Maximize minimum sweetness in cake cutting
Given that cake consists of N chunks, whose individual sweetness is represented by the sweetness[] array, the task is to cut the cake into K + 1 pieces to maximize the minimum sweetness.
Examples:
Input: N = 6, K = 2, sweetness[] = {6, 3, 2, 8, 7, 5}
Output: 9
Explanation: Divide the cake into [6, 3], [2, 8], [7, 5] with sweetness levels 9, 10, and 12 respectively.Input: N = 7, K = 3, sweetness[] = {1, 2, 4, 7, 3, 6, 9}
Output: 7
Explanation: Divide the cake into [1, 2, 4], [7], [3, 6], [9] with sweetness levels 7, 7, 9, and 9 respectively.
Approach: This can be solved with the following idea:
The approach used is the binary search to find the maximum sweetness value that can be achieved after dividing the given array of sweetness values into k + 1 groups, where each group has a minimum sweetness value of mn_value.
Steps involved in the implementation of code:
- First, we initialize the variables “sum” and “mn_value” to calculate the sum of all sweetness levels and the minimum sweetness level in the array respectively.
- We set the low and high values of binary search as 1 and sum respectively.
- We perform a binary search on the range [low, high] until low > high. In each iteration, we calculate the mid-value and call the “canSplit” function to check if the array can be split into k+1 subarrays where the minimum sweetness level of each subarray is at least mid.
- If “canSplit” returns true, we store the current mid value as the answer and update the low value to mid+1 to search for larger mid values.
- Otherwise, if “canSplit” returns false, we set the high value to mid-1 to search for smaller mid-values.
- Finally, we return the answer.
Below is the implementation of the above approach:
C++
// C++ Implementation #include <iostream> #include <vector> #include<climits> using namespace std; // Function to check whether split is possible bool canSplit(vector< int >& sweetness, int mn_value, int k) { int curr = 0; int cnt = 0; for ( int i = 0; i < sweetness.size(); i++) { curr += sweetness[i]; if (curr >= mn_value) { cnt++; curr = 0; } } return cnt >= k + 1; } // Function to maximize the minimum sweetness int maxSweetness(vector< int >& sweetness, int n, int k) { int sum = 0; int mn_value = INT_MAX; for ( int i = 0; i < n; i++) { sum += sweetness[i]; mn_value = min(mn_value, sweetness[i]); } int low = 1; int high = sum; int ans = 0; while (low <= high) { int mid = (low + high) / 2; // If split is possible if (canSplit(sweetness, mid, k)) { ans = mid; low = mid + 1; } else { high = mid - 1; } } return ans; } // Driver code int main() { vector< int > sweetness = { 6, 3, 2, 8, 7, 5 }; int n = sweetness.size(); int k = 2; // Function call int result = maxSweetness(sweetness, n, k); cout << result << endl; return 0; } // This code is contributed by akshitaguprzj3 |
Java
// Java Implementation public class GFG { // Function to check whether split is // possible public static boolean canSplit( int [] sweetness, int mn_value, int k) { int curr = 0 ; int cnt = 0 ; for ( int i = 0 ; i < sweetness.length; i++) { curr += sweetness[i]; if (curr >= mn_value) { cnt++; curr = 0 ; } } return cnt >= k + 1 ; } // Function to maximize the // minimum sweetness public static int maxSweetness( int [] sweetness, int n, int k) { int sum = 0 ; int mn_value = Integer.MAX_VALUE; for ( int i = 0 ; i < n; i++) { sum += sweetness[i]; mn_value = Math.min(mn_value, sweetness[i]); } int low = 1 ; int high = sum; int ans = 0 ; while (low <= high) { int mid = (low + high) / 2 ; // If split is possible if (canSplit(sweetness, mid, k)) { ans = mid; low = mid + 1 ; } else { high = mid - 1 ; } } return ans; } // Driver code public static void main(String[] args) { int [] sweetness = { 6 , 3 , 2 , 8 , 7 , 5 }; int n = sweetness.length; int k = 2 ; // Function call int result = maxSweetness(sweetness, n, k); System.out.println(result); } } |
Python3
# Python3 Implementation def canSplit(sweetness, mn_value, k): # Variable to track the current sweetness sum curr = 0 # Variable to count the number of splits cnt = 0 for i in range ( len (sweetness)): curr + = sweetness[i] if curr > = mn_value: cnt + = 1 curr = 0 # Check if the number of splits is greater than or equal to k+1 return cnt > = k + 1 def maxSweetness(sweetness, n, k): # Variable to store the total sweetness sum total_sum = 0 # Variable to store the minimum sweetness value mn_value = float ( 'inf' ) for i in range (n): total_sum + = sweetness[i] mn_value = min (mn_value, sweetness[i]) # Initialize the search range low = 1 high = total_sum ans = 0 while low < = high: # Calculate the midpoint mid = (low + high) / / 2 # If split is possible if canSplit(sweetness, mid, k): ans = mid low = mid + 1 else : high = mid - 1 # Return the maximum sweetness value return ans # Driver code # Input sweetness array sweetness = [ 6 , 3 , 2 , 8 , 7 , 5 ] n = len (sweetness) k = 2 # Function call result = maxSweetness(sweetness, n, k) print (result) # This code is contributed by akshitaguprzj3 |
C#
// c# Implementation using System; namespace GFG { class Program { // Function to check whether split is possible public static bool CanSplit( int [] sweetness, int mnValue, int k) { int curr = 0; int cnt = 0; for ( int i = 0; i < sweetness.Length; i++) { curr += sweetness[i]; if (curr >= mnValue) { cnt++; curr = 0; } } return cnt >= k + 1; } // Function to maximize the minimum sweetness public static int MaxSweetness( int [] sweetness, int n, int k) { int sum = 0; int mnValue = int .MaxValue; for ( int i = 0; i < n; i++) { sum += sweetness[i]; mnValue = Math.Min(mnValue, sweetness[i]); } int low = 1; int high = sum; int ans = 0; while (low <= high) { int mid = (low + high) / 2; // If split is possible if (CanSplit(sweetness, mid, k)) { ans = mid; low = mid + 1; } else { high = mid - 1; } } return ans; } // Driver code static void Main( string [] args) { int [] sweetness = { 6, 3, 2, 8, 7, 5 }; int n = sweetness.Length; int k = 2; // Function call int result = MaxSweetness(sweetness, n, k); Console.WriteLine(result); } } } |
Javascript
// Function to check whether split is possible function canSplit(sweetness, mn_value, k) { let curr = 0; let cnt = 0; for (let i = 0; i < sweetness.length; i++) { curr += sweetness[i]; if (curr >= mn_value) { cnt++; curr = 0; } } return cnt >= k + 1; } // Function to maximize the minimum sweetness function maxSweetness(sweetness, n, k) { let sum = 0; let mn_value = Infinity; for (let i = 0; i < n; i++) { sum += sweetness[i]; mn_value = Math.min(mn_value, sweetness[i]); } let low = 1; let high = sum; let ans = 0; while (low <= high) { let mid = Math.floor((low + high) / 2); // If split is possible if (canSplit(sweetness, mid, k)) { ans = mid; low = mid + 1; } else { high = mid - 1; } } return ans; } // Driver code const sweetness = [6, 3, 2, 8, 7, 5]; const n = sweetness.length; const k = 2; // Function call const result = maxSweetness(sweetness, n, k); console.log(result); // Nikunj Sonigara |
9
Time Complexity: O(n * log(sum))
Auxiliary Space: O(1)