# PCJ18D - Editorial

Tester: Prakhar Gupta
Editorialist: Prakhar Gupta

EASY

Binary Search

### PROBLEM:

Find out the minimum number of cookies to bake initially to eat at least N cookies, provided you can make 1 cookie from the crumbs of B cookies.

### QUICK EXPLANATION

We binary search on the number of cookies to bake initially.

### EXPLANATION:

To find the total number of cookies we eat if we have K cookies in the beginning, we use the following algorithm:

1. Initialise eaten = 0, crumbs = 0.

2. Eat all the cookies, i.e. eaten += K, crumbs += K.

3. Make new cookies from the crumbs, i.e. K = crumbs / B, crumbs = crumbs % B .

4. Repeat from step 2 if K > 0.

 int eaten = 0;
int crumbs = 0;

while(k > 0)
{
eaten += k;
crumbs += k;

k = crumbs / b;
crumbs %= b;
}
return eaten;


We start the binary search from lo = 1 and hi = N.

1. Find mid = \lfloor\frac{lo + hi} {2}\rfloor, and find total = cookies(mid).

2. If total < N, then set lo = mid + 1. Else, set hi = mid.

3. Repeat step 1 if lo < hi.

 int lo = 1;
int hi = n;

while(lo < hi)
{
int mid = (lo + hi) / 2;

if(total < n)
lo = mid + 1;
else
hi = mid;
}


Complexity: The time complexity is O(log(N) * log(B)) per test case.

### ALTERNATE SOLUTION:

You have N-1 crumbs available to eat at least N cookies since you won’t be able to use the crumbs of the last cookie. You can make a maximum of \lfloor\frac{N-1}{B}\rfloor extra cookies from the crumbs. So in all, you have to bake at least N - \lfloor\frac{N-1}{B}\rfloor cookies in the beginning.

Complexity: The time complexity is O(1) per test case.

### AUTHOR’S SOLUTIONS:

O(log(N) * log(B)) solution can be found here.
O(1) solution can be found here.

4 Likes

@madhav_1999 @prakhar17252 Can you guys pls post the editorial for PCJ18G ?? Help will be appreciated.

@na0013 The editorial for G has already been posted. Here is the link.

Thank You @prakhar17252 !!