### sinmish's blog

By sinmish, history, 2 months ago,

We are given an array of size N, we can delete a subset b1b2b3...bk from the array if 2^b1 + 2^b2 + …..2^bk = 2^x for non-negative integer x where ^ is the power operator. Find the minimum number of steps required to delete the complete array.

0 <= ai <= 1000000

1 <= N <= 1000000

• +1

 » 2 months ago, # |   0 Auto comment: topic has been updated by sinmish (previous revision, new revision, compare).
 » 2 months ago, # |   +1 So first observation is that answer is the number of set bits in $\sum2^{v[i]}$ for $i$ varies from $1$ to $n$. But since the values are large we cannot find it just by summation. We have to simulate the entire process of binary addition. For that sort the array and traverse from left. Initialize an empty array $val[1000001]$ with 0. Suppose we are at $v[i]$, add $1$ to $val[v[i]]$. Two cases may arise $val[v[i]]$ consists of 0, then change that to 1. Else if $val[v[i]]$ consists of 1, we have to make everything 0 till the next location of 0. And add 1 to the next location of 0. (That's how binary addition works). This assignment to 0 can be done using lazy segtree. But we need to also maintain next location of 0 for each 1 in an array say $nxt[1000001]$. Two cases arise. If $val[v[i]]$ is 0, then if $val[v[i]+1]$ is 0 then $nxt[v[i]]=v[i]+1$, or else $nxt[v[i]]=nxt[v[i]+1]$. If it is 1, then update $nxt[v[i]]$ in the same way as mentioned before. At the end, the number of 1 in the array $val$ is the answer. Code#include using namespace std; typedef long long ll; typedef long double ld; const ll maxn=1e6+10; const ll mod=1e9+7; const ll m2=1e9+7; const ll INF64 = ll(1e18); const ll max2=1e3+10; const ll N = 1000001; const ll MAXN=2e5+10; const ll ALPHABET_SIZE = 2; int nxt[maxn]; int val[maxn]; int main() { ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n,i,j; cin>>n; vector v(n); for(i=0;i>v[i]; } sort(v.begin(),v.end()); for(i=0;i