Sum of bit differences
PROBLEM :
Write a program to find the sum of bit differences in all pairs that can be formed from array elements n. Bit difference of a pair (x, y) is a count of different bits at same positions in binary representations of x and y. For example, bit difference for 2 and 7 is 2. Binary representation of 2 is 010 and 7 is 111 ( first and last bits differ in two numbers).
Input: The first line of input contains an integer T denoting the number of test cases. First line of the test case will contain an array of elements n.
Output: The sum of bit differences of all pairs that can be formed by given array.
Constraints:
1 <=T<= 100
1 <=N<= 10
1 <=a[i]<= 10
Example:
Input:
2
2
1 2
3
1 3 5
Output:
4
8
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<iostream>
using namespace std;
int main()
{
int t ;
cin>>t ;
while(t--){
int no ;
cin>>no ;
int arr[no] ;
for(int i=0;i<no;i++)
cin>>arr[i] ;
int ans=0 ;
for(int i=0;i<32;i++){
int count=0 ;
for(int j=0;j<no;j++){
if(arr[j]&(1<<i))
count++ ;
}
ans+=count*(no-count) ;
}
cout<<ans*2<<endl ;
}
return 0;
}
--------------------------------------------------------------------------------
Write a program to find the sum of bit differences in all pairs that can be formed from array elements n. Bit difference of a pair (x, y) is a count of different bits at same positions in binary representations of x and y. For example, bit difference for 2 and 7 is 2. Binary representation of 2 is 010 and 7 is 111 ( first and last bits differ in two numbers).
Input: The first line of input contains an integer T denoting the number of test cases. First line of the test case will contain an array of elements n.
Output: The sum of bit differences of all pairs that can be formed by given array.
Constraints:
1 <=T<= 100
1 <=N<= 10
1 <=a[i]<= 10
Example:
Input:
2
2
1 2
3
1 3 5
Output:
4
8
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<iostream>
using namespace std;
int main()
{
int t ;
cin>>t ;
while(t--){
int no ;
cin>>no ;
int arr[no] ;
for(int i=0;i<no;i++)
cin>>arr[i] ;
int ans=0 ;
for(int i=0;i<32;i++){
int count=0 ;
for(int j=0;j<no;j++){
if(arr[j]&(1<<i))
count++ ;
}
ans+=count*(no-count) ;
}
cout<<ans*2<<endl ;
}
return 0;
}
--------------------------------------------------------------------------------
Comments
Post a Comment