PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Yash Kulkarni
Testers: Abhinav Sharma, Venkata Nikhil Medam
Editorialist: Nishank Suresh
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)