Introduction:
You have one chocolate bar which consists of some pieces. Each piece has its sweetness given by the array of sweetness.
You're going to share this chocolate with your ‘K’ friends, so you need to cut ‘K’ times to get ‘K + 1’ pieces, each of which is made up of a continuous series of small parts.
You will eat the piece, which will have the minimum total sweetness, and give all the other pieces to your friends.
Find the maximum total sweetness of a piece you can get by cutting the chocolate bar optimally.
Let us see a few examples:-
Input 1:
[8, 7, 5, 4, 19, 10]
K = 2
Output 1:
10
Explanation 1: You can divide the chocolate to [8, 7], [5, 4, 19], [10]. You can pick a piece [10] with total sweetness = 10, with minimum sweetness among all pieces.
Input 2:
[5, 4, 3, 9, 10]
K = 2
Output 2:
9
Explanation 2: You can divide the chocolate to [5, 4], [3, 9], [10]. You can pick a piece [5, 4] with total sweetness = 9, with minimum sweetness among all pieces.
Input 3:
[3, 4, 19, 5, 34, 6, 10, 8]
K = 3
Output 3:
8
Recommended topic about, kth largest element in an array and Euclid GCD Algorithm
Approach 1:
The maximum sweetness you can get if you divide the chocolate is the sum of all the values of the sweetness array. Hence, we can run a for loop and try out all the possible values from i = 1 to i = sum(arr) if it is possible to divide the chocolate such that a piece with minimum sweetness is at least i.
Refer to the below implementation of the above approach.
class Main {
/*
function to find maximum sweetness
you get when you divide the chocolate
*/
public static int maximizeSweetness(int[] a, int k) {
int n = a.length;
/*
The sum will store the maximum
possible sweetness, you can get.
*/
int sum = 0;
for(int val : a) {
sum += val;
}
int ans = 0;
for(int i = 1; i <= sum; i++){
if(isPos(a, i, k + 1)){
ans = i;
}
}
return ans;
}
/*
Function to check if it is possible
to divide the chocolate such that you
get the minSweetness piece of chocolate.
*/
static boolean isPos(int[] arr, int minSweetness, int k){
int curSum = 0;
for(int i = 0; i < arr.length; i++){
curSum += arr[i];
if(curSum >= minSweetness){
// We have got one piece.
k--;
curSum = 0;
}
}
return k <= 0;
}
public static void main (String[] args) {
int array[] = {8, 7, 5, 4, 19, 10};
int k = 2;
int ans = maximizeSweetness(array, k);
System.out.println(ans);
}
}
Output:
Time Complexity: The time complexity of the above code is O(sum * N) because we are running a for loop of O(sum), and inside it, we are calling the isPos() function, which runs in O(N) time.
Space Complexity: The space complexity for the above approach is O(1) because we use constant space.
8+ registered 