Practice › Binary Search
Minimum Days to Make Bouquets
Medium · Binary Search · Asked at Google, Amazon, Microsoft
Flower i blooms on day bloom[i]. A bouquet needs k adjacent bloomed flowers, and each flower can be used in only one bouquet. Print the minimum number of days to wait to make m bouquets, or -1 if it is impossible.
Input
First line: n m k. Second line: the n bloom days.
Output
The minimum day, or -1.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ m ≤ 10^6
- 1 ≤ k ≤ n
- 1 ≤ bloom[i] ≤ 10^9
If m·k > n it is impossible. Otherwise binary search the day: for a given day, count bouquets greedily with runs of bloomed flowers.
Example 1
Input
5 3 1 1 10 3 10 2
Output
3
Example 2
Input
5 3 2 1 10 3 10 2
Output
-1
Hints
- If m·k > n there are not enough flowers — print −1. Otherwise waiting until the last bloom day always works.
- For a given day, count bouquets greedily: walk the row, extend a run of bloomed flowers, and cut a bouquet every k flowers. More days never means fewer bouquets — binary search the day.
Approach
can(day) scans the flowers, counting consecutive ones with bloom ≤ day; each time the run reaches k, make a bouquet and reset the run; an unbloomed flower also resets it. Binary search the smallest day in [min(bloom), max(bloom)] for which can is true. Check m·k > n with 64-bit arithmetic (m can be 10^6).
Complexity: O(n log(max bloom)) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n, m, k;
cin >> n >> m >> k;
vector<long long> b(n);
for (auto &x : b) cin >> x;
if (m * k > n) {
cout << -1 << "\n";
return 0;
}
auto can = [&](long long day) {
long long run = 0, made = 0;
for (long long x : b) {
if (x <= day) {
if (++run == k) made++, run = 0;
} else run = 0;
}
return made >= m;
};
long long lo = *min_element(b.begin(), b.end()), hi = *max_element(b.begin(), b.end());
while (lo < hi) {
long long mid = (lo + hi) / 2;
if (can(mid)) hi = mid;
else lo = mid + 1;
}
cout << lo << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, m, k, b = data[0], data[1], data[2], data[3:]
def can(day):
run = made = 0
for x in b:
if x <= day:
run += 1
if run == k:
made += 1
run = 0
else:
run = 0
return made >= m
if m * k > n:
print(-1)
else:
lo, hi = min(b), max(b)
while lo < hi:
mid = (lo + hi) // 2
if can(mid):
hi = mid
else:
lo = mid + 1
print(lo)Java solution
import java.util.*;
public class Main {
static long[] b;
static long m, k;
static boolean can(long day) {
long run = 0, made = 0;
for (long x : b) {
if (x <= day) {
if (++run == k) { made++; run = 0; }
} else run = 0;
}
return made >= m;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
m = sc.nextLong();
k = sc.nextLong();
b = new long[n];
long lo = Long.MAX_VALUE, hi = 0;
for (int i = 0; i < n; i++) {
b[i] = sc.nextLong();
lo = Math.min(lo, b[i]);
hi = Math.max(hi, b[i]);
}
if (m * k > n) {
System.out.println(-1);
return;
}
while (lo < hi) {
long mid = (lo + hi) / 2;
if (can(mid)) hi = mid;
else lo = mid + 1;
}
System.out.println(lo);
}
}Solve Minimum Days to Make Bouquets online · All practice problems