Problem Link:
Author: tseccodecell
DIFFICULTY:
Medium
PRE-REQUISITES:
Array Traversal, Binary Search
PROBLEM:
You are given N values of height of water containers. You need to fill water in these containers such that H_{i+1} = H_i + K where H_i is height of water filled in i^{th} container. You need to find the maximum value of K obtainable and maximum starting water height possible for that K.
QUICK EXPLANATION:
Perform binary search on the value of K to find the maximum value. Range of binary search can be from 0-10^{12} (or 0 to maximum value of H_i).
The maximum starting value can be found in O(n) by traversing the array and finding minimum difference between height of container and height of water filled for every index
EXPLANATION:
To find the largest value of K possible, we can iterate from 0-10^{12} and check with every value.
Whenever we find that a certain value of K is not possible, we will stop our iteration and the previous value of K will be the maximum obtainable.
This approach will work but will have huge time complexity.
So we will use binary search optimization to make this approach faster.
Binary search works here because the following condition is satisfied:
- if a value of K is not possible, then all greater values of K will not be possible
We apply apply binary search on the value of K in the range 0-10^{12}.
We first assign two variables, highest possible value = 0 & lowest impossible value = 10^{12} and then start binary search
For each K obtained, we check in O(n) whether this value of K is possible or not.
- If it is possible, we increase the highest possible to this value,
- otherwise we make the lowest impossible value to this value.
We continue this process until stopping condition of binary search is reached
At the end, the value of K will be in the highest possible variable
Now, fill the containers upto the required height using starting height of water filled as 1, then find the minimum difference of height of container and height of water filled among all containers. This can be done in O(n)
Adding that to the height of first container(1), we get the maximum starting value of the first container
Some test cases with answers:
Input:
5
3
1 9 100
3
2 100 4
5
20 10000000001 30000000004 40000000032 100000000543
5
1000 110000 1000000000 23424455 23334519
1
999
Output:
8 1
1 2
10000000000 1
109999 1
998 999
Time Complexity: O(nlogK + n) = O(nlogK), K range is from 0-10^{12}