## About the Problem

Setter(s) | Neelam Bugalia |

Tester(s) | Vichitr Gandas, Balajiganpathi S, Divyansh Verma |

Difficulty | Cakewalk |

Topics | Bit Manipulation |

Practice | Link |

Contest | Link |

## Solution Idea

As asked in the problem, people can get infected from each other only if absolute difference of number of set bits in the natural powers of the two persons is less than or equal to 1. Hence start with first person, find number of set bits for him, lets say its x then all people with number of set bits x will get infected. Also all the people with set bits x-1 and x+1 get infected. So from x first we will move to x-1 , x-2 ,… and so on. If for some y, there are no people with set bits y then this chain will break and none of the people with set bits < k will get infected. Similarly from x we will also move in other side i.e. x+1, x+2 ,... and so on. If for some y , there are no people with set bits y then this chain will break and none of the people with set bits > k will get infected.

This can be achieved with first finding count of how many people with set bits x for all possible x . And then looping on them as explained above.

### Complexity Analysis

Time Complexity: \mathcal{O}(n \log{n}) because of finding number of set bits for n people.

Space Complexity: \mathcal{O}(1) for storing count of people with set bits from 0 to 30.

## Codes

## Setter's Code

```
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
typedef long long int ll;
using namespace std;
int main()
{
int t; cin>>t;
assert(t <= 1e5);
int tot = 0;
while(t--){
int n; cin>>n;
assert(n <= 1e5);
tot += n;
vector<int> a(n);
for(int i=0;i<n;++i){
cin>>a[i];
assert(a[i] >= 0 and a[i] <= 1e9);
}
vector<int> f(35, 0);
for(int i=0;i<n;i++){
int x = __builtin_popcount(a[i]);
f[x]++;
}
int startBit = __builtin_popcount(a[0]);
int ans = f[startBit];
for(int i=startBit-1; i>=0;i--){
if(f[i] > 0)
ans += f[i];
else
break;
}
for(int i=startBit+1; i<35;i++){
if(f[i] > 0)
ans += f[i];
else
break;
}
cout<<ans<<'\n';
}
assert(tot <= 2e5);
return 0;
}
```

If you have used any other approach, share your approach in comments!

If you have any doubts, ask them in comments!