⬅ Previous Topic
Koko Eating BananasNext Topic ⮕
Find the Smallest Divisor Given a Threshold⬅ Previous Topic
Koko Eating BananasNext Topic ⮕
Find the Smallest Divisor Given a ThresholdTopic Contents
You are given an array bloomDay[]
where bloomDay[i]
represents the day on which the i-th
flower will bloom. Your task is to determine the minimum number of days required to make m
bouquets, where each bouquet requires k
adjacent bloomed flowers.
k
adjacent flowers to make each bouquet.If it's not possible to make m
bouquets, return -1
.
low
= minimum bloom day, high
= maximum bloom day.low ≤ high
.mid = (low + high) / 2
.m
bouquets in mid
days using a helper function:arr[i] ≤ mid
).k
adjacent, increment bouquet count and reset count.mid
as answer and move high = mid - 1
.low = mid + 1
.public class Bouquets {
public static boolean canMakeBouquets(int[] bloomDay, int m, int k, int day) {
int bouquets = 0, flowers = 0;
for (int b : bloomDay) {
if (b <= day) {
flowers++;
if (flowers == k) {
bouquets++;
flowers = 0;
}
} else {
flowers = 0; // Reset if bloom not ready
}
}
return bouquets >= m;
}
public static int minDays(int[] bloomDay, int m, int k) {
if ((long)m * k > bloomDay.length) return -1;
int low = Integer.MAX_VALUE, high = Integer.MIN_VALUE;
for (int day : bloomDay) {
low = Math.min(low, day);
high = Math.max(high, day);
}
int ans = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (canMakeBouquets(bloomDay, m, k, mid)) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans;
}
public static void main(String[] args) {
int[] bloom = {1, 10, 3, 10, 2};
int m = 3, k = 1;
System.out.println("Minimum Days: " + minDays(bloom, m, k));
}
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(n) | In the best case, the first binary search guess gives a valid answer after a single bouquet check. |
Average Case | O(n log(max_day - min_day)) | Binary search runs in log(max_day - min_day) steps and each step checks the full array to count bouquets. |
Worst Case | O(n log(max_day - min_day)) | Binary search iterates across the entire range of possible days, checking all n roses each time. |
O(1)
Explanation: Only a few variables are used; no extra space is needed apart from input.
⬅ Previous Topic
Koko Eating BananasNext Topic ⮕
Find the Smallest Divisor Given a ThresholdYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.