#include <bits/stdc++.h>
using namespace std;
int isKthBitSet(int n, int k)
{
if (n & (1 << (k - 1)))
return 1;
else
return 0;
}
int main() {
// your code goes here
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
long long int ans=0;
for(int i=32;i>=1;i–)
{
long long int count=0;
for(int j=0;j<n;j++)
{
if(isKthBitSet(a[j],i))
{
count++;
}
}
if(count>=2)
{
ans+=pow(2,i-1)(count(count-1)/2);
}
}
cout<<ans<<"\n";
return 0;
}
problem link?
I don’t’ actually understand what approach you are using to solve this problem. But a simple solution is we should keep a counter of the number whose ith bit is set. In this way, we will have an array arr of 32 size in which ith index will store how many numbers have their ith bit set.
Now traverse the original array again and for each number find its setbits. Let’s say the given number has bit 1,2 and 4 set now we will add to ans pow(2,1)*arr[1]+pow(2,2)*arr[2]+pow(2,4)*arr[4].
#include
#include
using namespace std;
#include<math.h>
#define ll long long int
int isKthBitSet(int n, int k)
{
if (n & (1 << (k - 1)))
return 1;
else
return 0;
}
int main()
{
ll size;
cin>>size;
ll arr[size];
for(ll j=0;j<size;j++)
{
cin>>arr[j];
}
ll ans=0;
for(ll j=32;j>=1;j–)
{
ll count=0;
for(ll h=0;h<size;h++)
{
if(isKthBitSet(arr[h],j))
{
count++;
}
}
if(count>=2)
{
ans+=pow(2,j-1)(count(count-1)/2);
}
}
cout<<ans<<"\n";
return 0;
}
I done it thank you
But still I have a small doubt why only we are using 32 bit y not 64 bit.
Because Ai <=10^6. Which will fit into 32 bit
bro can you tell me some resources to study begginer to bit manipulation.
I started from code monk: https://www.hackerearth.com/practice/basic-programming/bit-manipulation/basics-of-bit-manipulation/tutorial/ and practised some problems given there itself. After that you can learn from gfg, codeforces, topocder etc they have really nice tutorials on many advance and medium level topics.
bro i already completed the link you send yet now i have an another doubt
from hacker rank.
MY LOGIC
long sumXor(long n) {
long long int x=0,count=0;
while(x!=n)
{
if((x+n)==(x^n))
{
count++;
}
x++;
}
return count;
}
tells TLE
OTHER PEOPLE CODE
long sumXor(long n) {
long long int x=0,count=0;
while(n>0)
{
if((n&1)==0)
{
count++;
}
n>>=1;
}
return pow(2,count);
}
i understand the logic behind the code but i dont know to how get these type of logics for other questions, can anyone tell me best way to master only bit-Manipulation i am not that begginer completed a lot of videos and notes.
See here what is the given condition and break it down into the more simplified parts or conclusions.
Here we need to find out the total no. of pairs such that x+n == x^n and by seeing this equation we are sure that we have n as some fixed value and we need to check for the values of 0 <= x <= n.
Now derive some of the results from this equation,
x+n == x^n
Here on the left-hand side, we are adding the two nos. And on the right-hand side, we need to do the xor of the two nos. And now for an instant consider the binary representation of these nos.
If at a particular ith bit in n we get 0 and the same 0 we get for the ith bit in x the corresponding bit will also result in 0 in case of addition and xor.
0 + 0 = 0^0 [Required condition]
now suppose if at a particular ith bit in n we get 0 and 1 we get for the ith bit in x the corresponding bit will also result in 1 in case of addition and xor.
1 + 0 = 1^0 [Required condition]
now suppose if at a particular ith bit in n we get 1 and 0 we get for the ith bit in x the corresponding bit will result in 1 in case of addition and xor.
0 + 1 = 0^1 [Required condition]
now suppose if at a particular ith bit in n we get 1, and same 1 we get for the ith bit in x the corresponding ith bit will result in 0 in case of addition and 0 in xor.
1 + 1 != 1^1 [Not Required condition]
So we can say we need to count those nos. with which the & of x and n will be zero.
we need the pairs where x&n == 0
We can say that if a particular ith bit in n is 1, we definitely want 0 for the ith bit in x.
But if a particular ith bit in n is 0 then we have two choices either 0 or 1 will work for the ith bit in x.
We can say that count the no. of zeroes in the n (binary representation), and for all of them, we have two choices either 0 or 1 for that bit, so the answer is 2^(no. of zeroes in binary representation in n).
See its good that you have completed that tutorial but first understand that you need to solve a good number of questions to get decent hold of a certain topic. And by good number here i don’t mean 100+ super-easy problems. Try to solve questions that makes you think instead of just typing games.
Someone has already explained this particular problem so, i don’t think there is need of explaining it again and how to come to such solutions.