PROBLEM LINK:
Author: Madhav Sainanee
Tester: Prakhar Gupta
Editorialist: Prakhar Gupta
DIFFICULTY:
EASY
PREREQUISITES:
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:
I advise you to read about binary search from this article once.
To find the total number of cookies we eat if we have K cookies in the beginning, we use the following algorithm:
-
Initialise eaten = 0, crumbs = 0.
-
Eat all the cookies, i.e. eaten += K, crumbs += K.
-
Make new cookies from the crumbs, i.e. K = crumbs / B, crumbs = crumbs % B .
-
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.
-
Find mid = \lfloor\frac{lo + hi} {2}\rfloor, and find total = cookies(mid).
-
If total < N, then set lo = mid + 1. Else, set hi = mid.
-
Repeat step 1 if lo < hi.
int lo = 1; int hi = n; while(lo < hi) { int mid = (lo + hi) / 2; int total = cookies(mid, b); if(total < n) lo = mid + 1; else hi = mid; }
The answer will be hi.
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.