# PROBLEM LINK:

* Author:* Aman Gupta

*Pankaj Sharma*

**Tester:***Aman Gupta*

**Editorialist:**# DIFFICULTY:

CAKEWALK

# PREREQUISITES:

Basic observations, Math, Greedy

# PROBLEM:

Chef has to make cuts in Chocolate bar to make minimum K pieces. So that chef can make any length of Chocolate bar of 1\leq length \leq L by adding these pieces of chocolate bar.

Also, the length of pieces of chocolate bar should be in integer.

# QUICK EXPLANATION:

Chef has to make minimum k pieces from the length of chocolate bar L .

The approach is that any Length can be formed 1\leq length \leq L .By dividing the Length of chocolate bar in m+1 different numbers where m=log2(Length).

So the minimum no of pieces of chocolate bar are k=log2(Length)+1.

# EXPLANATION:

The key observation is that any number can be written using distinct powers of two’s.

Consider the length of a chocolate bar as a number N.

See proof here.

Now we have known that we need to split N as sum of distinct powers of two’s.

Now we need to choose minimum numbers by which we can make all numbers from 1 to N.

Now consider binary representation of N = 7 as 111.

We need 3 bits to represent all numbers from 1 to 7. So using 1, 2, 4 we can get all numbers from 1 to 7.

Now to represent all numbers from 1 to N we need only numbers equal to the total number of bits in N which is log_2 N + 1

what if N = 10 and something like this

Binary of 10 = 1010

Now we can use numbers like 1,2,4,3 and we can make all numbers from 1 to 4 using these 4. How ?

using 1,2,4 we can make 1 to 7 right?

So we using 7,6,5 made using 1,2,4 we can make 10,9,8 respectively.

So for general N having k bits we can make we can make all numbers from 1 to 2^{k-1} using k-1 bits and can get any number greater than that is from 2^{k-1}+1 to N by choosing last number as difference of N and required number.

So our answer will be log_2 N + 1

Now coming back to original problem

Lets understand by some examples.

The approach is that any Length can be formed from 1\leq length \leq L .By dividing the Length of chocolate bar in m+1 different numbers where m=log2(Length).

So chef has to cut chocolate bar into minimum k pieces where k=m+1. So that he can make any any size of chocolate bar from these pieces.

For example: Length of chocolate Bar is 6

log2(6) =2

So chef has to make 2 cuts in chocolate bar.These 2 cuts in chocolate bar can generators 3 pieces.

The chocolate bar can be cut into pieces of length 1,2,3 so that we can form any size of chocolate bar.

(1,2,3,4=3+1,5=3+2,6=1+2+3)

# SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
cout<<floor(log2(n))+1<<endl;
}
return 0;
}
```

## Tester's Solution

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << '\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << " = " << arg1 << " | "; __f(comma + 1, args...);
}
void solve() {
ll ans = 0;
ll n;
cin >> n;
ll max = 1e9;
assert(n >= 1 and n <= max);
while (n > 0) {
n /= 2;
ans++;
}
cout << ans << "\n";
}
int main()
{
cin.sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
assert(t >= 1 && t <= 100);
while (t--)
solve();
return 0;
}
```

For doubts, please leave them in the comment section, I’ll address them.