Problem: Given N elements, in one operation you can merge adjacent elements (i.e. sum them up into one element), you have to do exactly K operations, what is the minimum possible obtainable value of the maximum of the resultant array.
Example
Elements: 1 2 3
K : 1
Output: 3 (by merging 1 and 2 we get 3, if we merged 2 and 3 we would get 5 which is > 3)
I can do this problem in O(N^2) complexity by Dynamic Programming, but can better time complexity be achieved?
Problem Source? constraints?
How are you solving in N^2?
Create a min heap of all the elements in an array. Remove the top 2 elements, add them and insert in the heap. Do this k times.
Time Complexity: O(klogn)
Yes this would've worked but here we have the constraint that we are only allowed to merge adjacent elements, in your method we only merge two smallest element but they might not be necessarily adjacenct
Ohh Sorry I missed that part
I think you can solve this problem using binary search . Let's fix $$$mx$$$ , means the max element after performing $$$k$$$ operations would not be greater than $$$mx$$$ .
Now create a stack and start pushing elements in the stack . Now if the stack has at least 2 elements then take top 2 elements from the stack and check if there sum is less or equal to $$$mx$$$ . Now if the sum is less or equal to $$$mx$$$ , it means you can perform an operation here otherwise you can't .
Now in the end if you were able to perform $$$k$$$ operations then return $$$true$$$ otherwise return $$$false$$$ and set $$$low$$$ and $$$high$$$ of binary search accordingly .