Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. If m·k > n there are not enough flowers — print −1. Otherwise waiting until the last bloom day always works.
  2. 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