SET302 - Editorial

editorial
1

Problem Link - Problem-2 Practice Problem in 1600 to 1800 difficulty problems

Problem Statement:

The problem asks us to find the minimum number of laddoos K that Hrishi’s daughters can eat per hour such that they can finish all the laddoos from N sets within H hours.

Approach:

  1. Basic Insight:
  • For each set of laddoos A_i , if the daughters eat K laddoos per hour, the number of hours required to finish this set can be computed as: hours_needed (A_i)=(A_i+K−1)/K (integer division).The reason we use the formula is that they cannot eat a fraction of a laddoo set.
  1. Binary Search for the Minimum K:
  • To find the minimum K, we can perform binary search over possible values of K.
  • For each K in this range, we compute the total number of hours required to finish all laddoos, and check if it is less than or equal to H.

Algorithm:

  1. Feasibility Check: Calculate the total hours needed for a given K: total_hours = \sum_{i=1}^{N} \frac{A_i + K - 1}{K} the total hours is less than or equal to H, then the value K is feasible.

  2. Binary Search:

  • Set l=1and r=max⁡(A).
  • For each midpoint ‘mid’ in the binary search range, check if it is feasible using the check function.
  • If it’s feasible, try smaller values of K by setting r=mid−1.
  • If it’s not feasible, try larger values by setting l=mid+1.

Complexity:

  • Time Complexity: The binary search operates over the range of possible values for K, which is between 1 and the maximum number of laddoos in any set O(log(max_laddoos)). For each middle value K tested in the binary search, the check function iterates through the array A, which takes O(N) time. Total time complexity: O(N⋅log(max_laddoos)).
  • Space Complexity: O(1) No extra space required.