Divide the Chocolate

Nishant Rana
Last Updated: May 13, 2022

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

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.

Approach 2:

In the above approach, we are running a linear for loop and trying 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’. Instead of a linear search, we can apply Binary Search for this question to find the maximum sweetness piece we could get by dividing the chocolate. Suppose we can divide the chocolate such that we get the ‘X’ amount of sweetness. In that case, there is no need to check for the numbers less than ‘X.’ Similarly, if we are not able to divide the chocolate such that we don’t get ‘X’ amount of sweetness, there is no need to check for the numbers greater than ‘X.’
 

Refer to the below implementation for 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;
        
        int l = 0, h = 0;
        
        /*
          h will store the maximum 
          possible sweetness, you can get.
        */

        for(int val : a) {
            h += val;
        }
        
        int ans = 0;
        
        while(l <= h){
            
            /*
              We will check if we can get 
              get a piece with mid sweetness 
              if we divide the chocolate
            */
            int mid = l + (h - l)/2;
            
            if(isPos(a, mid, k+1)){
                ans = mid;
                l = mid+1;
            }
            else{
                h = mid-1;
            }
        }
        
        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 a[], int minSweetness, int k){
        int sum = 0;
        
        for(int i = 0;i < a.length;i++){
            sum += a[i];
            if(sum >= minSweetness){
                k--;
                sum = 0;
            }
        }
        
        return k<=0;
    }
    
public static void main (String[] args) {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int k = 5;
    int ans = maximizeSweetness(arr, k);
    System.out.println(ans);
}
}

 

Output:

 

Time Complexity: The time complexity of the above code is O(N * log(sum)) because we are running Binary Search while loop of O(log(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 are using the constant space.

FAQs:

  1. What optimization did we do on the brute force approach to solve this problem?
  • We applied binary search instead of linear search because if we are able to divide the chocolate such that we get the ‘X’ amount of sweetness, then there is no need to check for the numbers less than ‘X’. Similarly, if we are not able to divide the chocolate such that we don’t get the ‘X’ amount of sweetness, there is no need to check for the numbers greater than ‘X’.
     

2. What is the time complexity for the optimized approach?

  • The time complexity for the optimized approach2 is O(N * log(sum)) because we are doing a binary search in the range 1 to sum and inside it we are calling the isPos() function which runs in O(N) time.

Key Takeaways: 

In this blog, we have covered the following things:

  1. We first discussed the Brute Force approach to solve this problem.
  2. Then we saw how we optimized the brute force approach by applying Binary Search instead of a Linear Search.

 

If you want to learn more about Dynamic Programming and want to practice some questions which require you to take your basic knowledge on Dynamic Programming a notch higher, then you can visit our Guided Path for Binary Search. To practice this problem, you can visit Practice Problem.



Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think