Divide Chocolates

The idea is to figure out the recursive calls and optimize them using dynamic programming.

It breaks down into a problem of dividing the array into ‘K’ + 1 partitions such that the partition which has the lowest sum of sweetness is maximum as compared to all the possible partitions. It’s better to make a prefix array as we would need the prefix sum of the array in every iteration. 

Now, we will start from the bottom, and then we will find the final answer. We will find the answer for breaking the subarray from indices from 0 to ‘i’ into ‘j’ parts where ‘i’ lies from 0 to ‘N’ - 1 and ‘j’ lies from 0 to a minimum of ‘M’ and ‘i’ + 1.

There is a base condition: If the number of chunks is less than the number of desired divisions, then Ninja won’t get any chunks. So, the answer will be 0.

The steps are as follows:

• Base Condition: If ‘K’ is greater than or equal to the number of chunks in the array ‘ARR’, return 0.
• Increment ‘K’ by 1 as there are ‘K’ friends and the number of partitions expected is ‘K’ + 1.
• Calculate the prefix sum of the given array and store it in an array ‘PREFIXSUM’ as we will require it in every iteration. Otherwise, it will increase the time complexity.
• Initialize a matrix ‘DP’ with the number of rows = ‘N’ and the number of columns = ‘K’ + 1 to the minimum integer value. In this matrix ‘DP[i][j]’ stores the sweetness of the part whose sum of sweetness is minimum after dividing the subarray from indices 0 to ‘i’ into ‘j’ parts. So, for any ‘i’, the 0'th part is not used for all ‘i’ in the range 0 to ‘N’ - 1.
• Iterate from ‘i’ = 0 to ‘N’ - 1 and fill the first column with the prefix sum of the respective indices.
• Iterate from ‘i’ = 1 to ‘N’ - 1:
  • Iterate from ‘j’ = 2 to a minimum of ‘K’ and ‘i’ + 1:
    • Now, we will break the subarray from indices ‘0’ to ‘l’ into ‘j’ - 1 part and then ‘l’ + 1 to ‘i’ into 1 part for all ‘l’ in the range 0 to ‘i’ - 1.
    • Iterate from ‘l’ = 0 to ‘i’ - 1:
      • Store the value of prefix sum from ‘l’ + 1 to ‘i’ + 1 in a variable ‘TEMP’.
      • Update the value of ‘TEMP’ to the minimum of ‘TEMP’ and 'DP[l][j-1]'.
      • Update the value of ‘DP[i][j]’ to the maximum of ‘DP[i][j]’ and ‘TEMP’.
• Return ‘DP[N-1][M]’ as the final answer as this is the answer for breaking the array arr from 0 to ‘N’ - 1 into ‘M’ parts.

The idea is to find the range in which the minimum sweetness can lie and then iterate in the given range and find the maximum sweetness you can have. The minimum value possible of sweetness is the minimum sweetness in the given array ‘ARR’, and the maximum value of sweetness is the sum of the sweetness of the chunks in the array ‘ARR’. The goal is to maximize the minimum sweetness one can have. Then use binary search to maximize the minimum sweetness of the divided chunks. The reason is that the range ‘MINSWEETNESS’ to ‘MAXSWEETNESS’ is a sorted range. So, if we can use binary search, then we can cut down the time complexity from O('SUM') to O(log('SUM')) for searching, which increases the efficiency.

There is a base condition: If the number of chunks is less than the number of desired divisions, then Ninja won’t get any chunks. So, the answer will be ‘0’.

The steps are as follows:

• Base Condition: If ‘K’ is greater than or equal to the number of chunks in the array ‘ARR’, return ‘0’.
• Increment ‘K’ by ‘1’ as there are ‘K’ friends and the number of divisions required is ‘K’ + 1.
• Initialize ‘MINSWEETNESS’ = the minimum sweetness in the given array ‘ARR’ and ‘MAXSWEETNESS’ = sum of all the sweetness of the array ‘ARR’.
• Execute a while loop with the condition that ‘MAXSHIPCAPACITY’ >= ‘MINSHIPCAPACITY’:
• Initialize ‘MIDSWEETNESS’ = ('MINSWEETNESS' + ‘MAXSWEETNESS’)/2.
• Check if the given value of ‘MINSWEETNESS’ is taken as the sweetness then Will the distribution be possible?
  • Define a function ‘CHECKVALIDITY’ which takes three arguments ‘TARGETSWEETNESS’, ‘NUMS’, and ‘K’, which denotes the sweetness value for which you are checking, the given array ‘NUMS’, and the number of friends you have.
  • Initialize two variables, ‘CURRENTFRIENDNUMBER’ equal to '1' and ‘CURRENTSWEETNESS’ to '0', which denotes the current friend number for which we are checking, and the sweetness that the friend has.
  • Iterate over the array ‘ARR’:
    • Check if, after adding the current sweetness, the total sweetness for the current friend exceeds the ‘TARGETSWEETNESS’ or not.
    • If it doesn’t exceed, then add the current sweetness to ‘CURRENTSWEETNESS’.
    • If it exceeds, then increase the current friend number and check for the next friend, and then set ‘CURRENTSWEETNESS’ to the value of the current sweetness in the array ‘ARR’.
    • If ‘CURRENTFRIENDNUMBER’ becomes greater than or equal to ‘K’, it means that the division is possible. So, we will return ‘true’.
  • Otherwise, we will return 'false'.
  • If the function returns ‘true’, then we will update the value of ‘MINSWEETNESS’ to ‘MIDSWEETNESS’. Otherwise, we will update the value of ‘MAXSWEETNESS’ to ‘MAXSWEETNESS’ - 1.
  • Now, if the given value of ‘MAXSWEETNESS’ is taken as the sweetness is possible, return ‘MAXSWEETNESS’ as the final answer.
  • Otherwise, return ‘MINSWEETNESS’ as the final answer.