Given a garden with N different flowers, where each flower will bloom on ith day as specified in the bloomDay[] array. To create one bouquet, you need to pick K adjacent flowers from the garden. You want to make a total of M bouquets. The task is to find the minimum number of days you need to wait to make M bouquets from the garden. If it’s impossible to create M bouquets, return -1.
Examples:
Input: M = 2, K = 3, bloomDay = [5, 5, 5, 5, 10, 5, 5]
Output: 10
Explanation: As we need 2 (M = 2) bouquets and each should have 3 flowers, After day 5: [x, x, x, x, _, x, x], we can make one bouquet of the first three flowers that bloomed, but cannot make another bouquet. After day 10: [x, x, x, x, x, x, x], Now we can make two bouquets, taking 3 adjacent flowers in one bouquet.Input: M = 3, K = 2, bloomDay = [1, 10, 3, 10, 2]
Output: -1
Explanation: As 3 bouquets each having 2 flowers are needed, that means we need 6 flowers. But there are only 5 flowers so it is impossible to get the needed bouquets therefore -1 will be returned.
Minimum days to make M bouquets using Binary Search:
The idea is to use Binary search on answer. Our search space would be start = 0 to end = some maximum value, which represent the range of minimum number of required days. Now, calculate mid and check if mid days is possible to make M bouquet such that K flowers are adjacent to make a bouque. If possible then update the result with mid value and movde the search space from end to mid – 1. otherwise, move start to mid + 1.
Step-by-step approach:
- A function, isValid(), checks if a given number of days (x) allows creating M bouquets or not.
- Binary search begins with the start = 0 and end to large value (1e7).
- Calculate mid = (start + end) /2, and Check:
- If mid is valid, it becomes the new result, and the search range adjusts to the left (end = mid – 1).
- If mid is not valid, the search range shifts to the right (start = mid + 1).
- This process continues until the minimum required days are found and returned.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function to check if the given// number of days (x) is valid for// creating bouquetsbool isValid(int x, vector<int>& arr, int K, int M){ int result = 0; int prevCount = 0; // Iterate through the bloom // days of the flowers for (int i = 0; i < arr.size(); i++) { if (arr[i] <= x) { prevCount += 1; } else { // If the current bloom day // is greater than x, update // the result and reset prevCount result += prevCount / K; prevCount = 0; } } result += prevCount / K; // Check if the result is greater // than or equal to the desired // number of bouquets (M) if (result >= M) return true; return false;}// Function to find the minimum number// of days needed to create M bouquetsint minDaysBloom(vector<int>& arr, int K, int M){ int start = 0, end = 1e7; int result = -1; while (start <= end) { int mid = (start + end) / 2; if (isValid(mid, arr, K, M)) { // If the current mid is // valid, update the result // and adjust the search range result = mid; end = mid - 1; } else { // If the current mid is // not valid, adjust the // search range start = mid + 1; } } return result;}// Drivers codeint main(){ vector<int> arr = { 1, 2, 4, 9, 3, 4, 1 }; int K = 2, M = 2; // Find and output the minimum // number of days needed to // create M bouquets cout << minDaysBloom(arr, K, M); return 0;} |
Java
// Java code for the above approach:class GFG { // Function to check if the given // number of days (x) is valid for // creating bouquets static boolean isValid(int x, int[] arr, int K, int M) { int result = 0; int prevCount = 0; // Iterate through the bloom // days of the flowers for (int i = 0; i < arr.length; i++) { if (arr[i] <= x) { prevCount += 1; } else { // If the current bloom day // is greater than x, update // the result and reset prevCount result += prevCount / K; prevCount = 0; } } result += prevCount / K; // Check if the result is greater // than or equal to the desired // number of bouquets (M) if (result >= M) return true; return false; } // Function to find the minimum number // of days needed to create M bouquets static int minDaysBloom(int[] arr, int K, int M) { int start = 0, end = (int)1e7; int result = -1; while (start <= end) { int mid = (start + end) / 2; if (isValid(mid, arr, K, M)) { // If the current mid is // valid, update the result // and adjust the search range result = mid; end = mid - 1; } else { // If the current mid is // not valid, adjust the // search range start = mid + 1; } } return result; } // Drivers code public static void main(String[] args) { int[] arr = { 1, 2, 4, 9, 3, 4, 1 }; int K = 2, M = 2; // Find and output the minimum // number of days needed to // create M bouquets System.out.println(minDaysBloom(arr, K, M)); }}// This code is contributed by ragul21 |
Python3
# Python Implementation:def isValid(x, arr, K, M): result = 0 prevCount = 0 # Iterate through the bloom days of the flowers for i in range(len(arr)): if arr[i] <= x: prevCount += 1 else: # If the current bloom day is greater than x, update the result and reset prevCount result += prevCount // K prevCount = 0 result += prevCount // K # Check if the result is greater than or equal to the desired number of bouquets (M) if result >= M: return True return Falsedef minDaysBloom(arr, K, M): start = 0 end = 1e7 result = -1 while start <= end: mid = (start + end) // 2 if isValid(mid, arr, K, M): # If the current mid is valid, update the result and adjust the search range result = mid end = mid - 1 else: # If the current mid is not valid, adjust the search range start = mid + 1 return resultarr = [1, 2, 4, 9, 3, 4, 1]K = 2M = 2# Find and output the minimum number of days needed to create M bouquetsprint(minDaysBloom(arr, K, M))# This code is contributed by Tapesh(tapeshdua420) |
C#
using System;using System.Collections.Generic;class Program{ // Function to check if the given // number of days (x) is valid for // creating bouquets static bool IsValid(int x, List<int> arr, int K, int M) { int result = 0; int prevCount = 0; // Iterate through the bloom // days of the flowers foreach (int bloomDay in arr) { if (bloomDay <= x) { prevCount += 1; } else { // If the current bloom day // is greater than x, update // the result and reset prevCount result += prevCount / K; prevCount = 0; } } result += prevCount / K; // Check if the result is greater // than or equal to the desired // number of bouquets (M) return result >= M; } // Function to find the minimum number // of days needed to create M bouquets static int MinDaysBloom(List<int> arr, int K, int M) { int start = 0, end = (int)1e7; int result = -1; while (start <= end) { int mid = (start + end) / 2; if (IsValid(mid, arr, K, M)) { // If the current mid is // valid, update the result // and adjust the search range result = mid; end = mid - 1; } else { // If the current mid is // not valid, adjust the // search range start = mid + 1; } } return result; } // Driver code static void Main() { List<int> arr = new List<int> { 1, 2, 4, 9, 3, 4, 1 }; int K = 2, M = 2; // Find and output the minimum // number of days needed to // create M bouquets Console.WriteLine(MinDaysBloom(arr, K, M)); }} |
Javascript
function isValid(x, arr, K, M) { let result = 0; let prevCount = 0; // Iterate through the bloom days of the flowers for (let i = 0; i < arr.length; i++) { if (arr[i] <= x) { prevCount += 1; } else { // If the current bloom day is greater than x, // update the result and reset prevCount result += Math.floor(prevCount / K); prevCount = 0; } } result += Math.floor(prevCount / K); // Check if the result is greater than or equal // to the desired number of bouquets (M) return result >= M;}function minDaysBloom(arr, K, M) { let start = 0; let end = 1e7; let result = -1; while (start <= end) { const mid = Math.floor((start + end) / 2); if (isValid(mid, arr, K, M)) { // If the current mid is valid, update the result // and adjust the search range result = mid; end = mid - 1; } else { // If the current mid is not valid, adjust the search range start = mid + 1; } } return result;}const arr = [1, 2, 4, 9, 3, 4, 1];const K = 2;const M = 2;// Find and output the minimum number of days // needed to create M bouquetsconsole.log(minDaysBloom(arr, K, M)); |
Output
4
Time complexity: O(N*log(MaxDays)), where N is the number of elements in the ‘arr’ vector, and MaxDays is the maximum possible number of days for a rose to bloom.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
