can anyone explain logic to solve this??

general
1

http://codeforces.com/contest/588/problem/C

2

i found this solution but i am not getting it…
#include <bits/stdc++.h>
// #define endl ‘\n’
using namespace std;

typedef long long ll;
typedef vector vi;
typedef map<long long, long long> mii;

const long long N = 1000107;

long long a[N];

int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
long long n;
cin>>n;
long long sum = 0;
for(long long i = 0; i < n; i++){
long long x;
cin>>x;
a[x]++;
}
for(long long i = 0; i < N; i++){
if(a[i]>1){
a[i+1] += a[i]/2;
a[i] %= 2;
}
}
long long ans = 0;
for(long long i = 0; i <= N; i++){
if(a[i] == 1){
ans++;
}
}
cout<<ans<<endl;
}

3

Hi,
The basic idea to solve this question is to express the numbers in binary. This is quite intuitive as you can directly write the number as sum of powers of two, when it is expressed in binary.
Another insight required is that when you add two numbers, the number of 1’s in the binary representation of the sum is a direct indicator as to how many powers of two could not be combined together. This will become more clear by taking examples:

2 + 4 = 6(110) No. of set bits = 2. So there were no combinations
but
4 + 4 = 8(1000) No. of set bits = 1. So there was a combination

You can try taking more numbers together and convince yourself.

The solution you have does the same thing. It first finds the binary representation of the sum (which is easy as the numbers are already in the form of power of 2 so there binary representation has just one bit on). Then we simply count the number of set bits in the sum which is the answer.

Hope this helps!

1 Like
4

Hi, I used a similar approach as the one you found
here is my code http://ideone.com/efX290
The basic intution is to form pairs and know that two 2^i s can promoted to one 2^(i+1).
So if you have 3 3 3 3 4 4 5 5
the pairs of 3s can be promoted to half the number of 4s, and hence your array should now be 4 4 4 4 5 5
Do the same with the 4s, and you will get 5 5 5 5, which will eventually become just one 7
So in the end you count the number of 1s in your count array to find the isolated numbers which need to be lifted at once.