SPLITN - Editorial

editorial
,
1

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)
1 Like
2

can anyone explain whats wrong in this approch

void solve() {
  int n;
      cin>>n;;
      int count=1;
    
      if(ceil(log2(n)) == floor(log2(n))){
        cout<<0<<endl;
      }
      else{
        int k=n-power(2,floor(log2(n)));
       
        while(k>2){
          int p=k-power(2,floor(log2(k)));
          k=p;
          count++;
        }
        cout<<count<<endl;
      }  

}
4

//can anybody tell me why this code is showing wrong answer

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll func(ll n)
{
while(n%2==0)
{
n=n/2;
}
if(n==1)//it is already in power of 2
return 1;
else return 0;
}
void solve()
{
ll n;
cin>>n;
if(func(n))
{
cout<<“0”<<endl;
}
else
{
ll temp=n;
ll ctr=0;
while(temp>1)
{
temp/=2;
ctr++;
}
ll diff=n-pow(2,ctr);
if(func(diff))
{
cout<<“1”<<endl;
}
else
{
cout<<“2”<<endl;
}
}
}
int main()
{

int t;
cin>>t;
while(t--)
{
    solve();
}
return 0;

}

5

return statement isn’t there in solve function! Please check.

1 Like
6

it’s void function therefore return is not required.