# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Yash Kulkarni

*Abhinav Sharma, Venkata Nikhil Medam*

**Testers:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

1195

# PREREQUISITES:

Knowledge of the binary number system

# PROBLEM:

Kulyash has an integer N. In one operation, he can take an integer X he has and break it into two integers Y and Z whose sum is X. Find the minimum number of operations needed so that every integer with him is a power of 2.

# EXPLANATION:

Note that each operation performed doesnâ€™t change the sum of all the numbers Kulyash has. In particular, the sum is always going to be N.

At the final state, when everything is a power of 2, this means that we have written N as the sum of some powers of 2. So, if we are able to find the minimum number of powers of 2 needed to write N, we will then be able to find our answer â€” if we need K powers of 2 to sum up to N, the answer is K-1 because we can create one of these powers at each step (and the last step will create two).

So, what is the minimum number of powers of 2 needed?

## Answer

Write N in binary. If it has K set bits, then we need at least K powers of 2 to sum up to N.

The proof of this should be fairly easy to see if you are familiar with the binary number system, but is included below for completeness.

## Proof

Suppose we write N = x_1 + x_2 + \ldots + x_m, where each x_i is a power of 2. If some two of the x_i are equal, we can combine them into a single larger power of 2 and obtain a sum of N with m-1 powers of 2 instead.

Hence, when N is written as the sum of the lowest possible number of powers of 2, all these powers must be distinct. However, by the property of the binary number system, there is **exactly one** way to write a number as the sum of distinct powers of 2.

This completes the proof.

Once we know the above, the implementation is fairly simple. Count the number of set bits in the binary representation of N (either by looping over each bit or using some inbuilt function), let this be K. The answer is then K-1.

# TIME COMPLEXITY:

\mathcal{O}(\log N) or \mathcal{O}(1) per test case.

# CODE:

## Tester (C++)

```
// Tester: Nikhil_Medam
#include <bits/stdc++.h>
#pragma GCC optimize ("-O3")
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
#define double long double
const int N = 1e5 + 5;
int t, n;
int32_t main() {
cin >> t;
while(t--) {
cin >> n;
cout << __builtin_popcount(n) - 1 << endl;
}
return 0;
}
```

## Editorialist (Python)

```
for _ in range(int(input())):
n = int(input())
print(bin(n).count('1') - 1)
```