Cost to Cut a Chocolate

Hard
0/120
Average time to solve is 30m
profile
Contributed by
99 upvotes
Asked in companies
FacebookMedia.net

Problem statement

You are given chocolate of ‘N’ length. The chocolate is labeled from 0 to ‘N’. You are also given an array ‘CUTS’ of size ‘C’, denoting the positions at which you can do a cut. The order of cuts can be changed. The cost of one cut is the length of the chocolate to be cut. Therefore, the total cost is the sum of all the cuts. Print the minimum cost to cut the chocolate.

Note:

All the integers in the ‘CUTS’ array are distinct.
For example: 
Let ‘N’ be: 4
Let the ‘CUTS’ array be: [1, 3].

Let the order of doing the cut be [1, 3].
The first cut of 1 on length 4 results in a cost of 4, and chocolate is split into two parts of the length of 1 and 3.
The second cut of 3 on length 3 results in a cost of 3, and chocolate is split into two parts again of the length of 2 and 1. So the total cost is 7.

The cost will remain the same if we change the order of cutting. So the result is 7.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘C’, representing the length of chocolate and size of the ‘CUTS’ array.

The second line of each test case contains ‘C’ space-separated integers, representing the array ‘CUTS’ elements.
Output Format : 
For each test case, print the minimum cost to cut the chocolate.

Print output of each test case in a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
2 <= N <= 10^5
1 <= C <= 10^3
1 <= CUTS[i] <= N - 1

Time Limit: 1 sec
Sample Input 1 :
2
4 2
1 3
5 3
1 3 4
Sample Output 1 :
7
10
Explanation For Sample Output 1 :
For test case 1: 
Let the order of doing the cut be [1, 3].
The first cut of 1 on length 4 results in a cost of 4, and chocolate is split into two parts of the length of 1 and 3.
The second cut of 3 on length 3 results in a cost of 3, and chocolate is split into two parts again of the length of 2 and 1. So the total cost is 7.

The cost will remain the same if we change the order of cutting. So the result is 7.

For test case 2: 
Let the order of doing the cut be [1, 3, 4].
The first cut of 1 on length 5 results in a cost of 5, and chocolate is split into two parts of the length of 1 and 4.
The second cut of 3 on length 4 results in a cost of 4, and chocolate is split into two parts again of the length of 2 and 2. The total cost is 9.
The third cut of 4 on length 2 results in a cost of 2, and chocolate is split into two parts again of the length of 1 and 1. The total cost is 11.

The minimum cost will be 10 when the order of doing cuts will be: [3, 1, 4].
Sample Input 2 :
2
10 4
1 3 4 7
10 2
1 3
Sample Output 2 :
23
13
Hint

Try to check all orders to do the cuts.

Approaches (3)
Brute Force

The basic idea is to find all the cuttings orders and select the minimum out of them. If we have chocolate of starting index (say, ‘startIdx’) and ending index (‘endIdx’), we divide it into two parts by cutting it at any given point. We check all the places we can cut, take the minimum of them, and add the current length of the chocolate. The base case will be when the size of chocolate is less than equal to 1 as it cannot be cut further into smaller pieces.
 

Here is the algorithm :

 

  1. Insert 0 and ‘N’ in the ‘CUTS’ array to include the chocolate length.
  2. Sort the ‘CUTS’ array.
  3. Call the HELPER function to find the minimum cost and return the value returned by the function.

 

HELPER(‘N’, ‘CUTS’, ‘startIdx’, ‘endIdx’)  (where ‘startIdx’ and ‘endIdx’ and the positions we do the cuts)

 

  1. Base case:
    • Check if ‘endIdx’ - ‘startIdx’ is smaller than or equal to 1.
      • Return 0.
  2. Create a variable (say, ‘totalCost’) to store the total cost and initialize it with some large value.
  3. Run a loop from ‘startIdx’ + 1 to ‘endIdx’ (say, iterator ‘i’) to cut the ‘ith’ position.
    • Recursively call the HELPER function and update the value of ‘endIdx’ to ‘i’ and store the value returned by the function in a variable (say, ‘COST1’).
    • Recursively call the HELPER function and update the value of ‘startIdx’ to ‘i’ and store the value returned by the function in a variable (say, ‘COST2’).
    • Update ‘totalCost’ with the minimum of ‘totalCost’ and sum of ‘COST1’ and ‘COST2’.
  4. Add (‘CUTS[endIdx]’ - ‘CUTS[startIdx]’) to the ‘totalCost’ to include the length of the chocolate.
  5. Return ‘totalCost’.
Time Complexity

O(C!), where ‘C’ is the number of cuts.
 

We check all the permutations of cutting, which takes O(C!) time. We also sort the ‘CUTS’ array, which takes O(C*log(C)) time. Therefore, the overall time complexity will be O(C!).

Space Complexity

O(C), where ‘C’ is the number of cuts.

 

The recursion stack of the HELPER function can be maximum O(C). Therefore, the overall space complexity will be O(C).

Code Solution
(100% EXP penalty)
Cost to Cut a Chocolate
Full screen
Console