Can someone please help me understand the below solution.
Problem statement --> Array Division
Solution on GitHub --> Solution Here
After mulling over it and trying to find out what the code does leaves me with the following understanding.
A binary search is used to find the desired maxnumber which obviously lies between max(array) and sum of all elements of the array.
somehow only for the desired maxnumber the number of sets (counter) calculated with the condition equals the input k:
if (currentsum + currentelement > maxnumber)
counter++;
currentsum = 0;
Can someone please explain to me the relation between the maxnumber and number of sets (k), which is exploited in this solution ? It would be of immense help. Thanks in advance!
Hello, assume you have a max_sum. Then you can divide the array into some number x of subarrays such that every subarray has sum < max_sum. If you increase the max_sum, then the number of subarrays either says the same or decreases. (Why?)
So you can binary search on max_sum until x is equal to k.
Okay, thanks for the explanation. I think the answer to why is intuitive.. if max_sum is increased then more elements are required for each subarray, so that decreases the number of subarrays. How can it be the same though?
It’s possible that after increasing the max sum, the number of subarrays doesn’t change.
For example:
n=4, a=[10,11,12,13]
If max_sum=27, then we subarrays [10,11] and [12,13]. If we raise max_sum to 28, the subarrays don’t change. Only when max_sum reaches 33 does the subarray change.
That loop simply sums up all the elements. Whenever the sum becomes bigger x the sum is reset to 0, and cnt is incremented. So it counts the number of groups when the sum of each group is maximal but still <=x.
If that count is smaller/equal k then it is possible to build k groups with max sum x, else it is not.
I understand the implementation of the code. My question is why it works? WhyIf that count is smaller/equal k then it is possible to build k groups with max sum x, else it is not?
The loop counts the smallest possible number of groups for a given x.
Assume the first element in the array, a[0]. It must belong to a group. So we have a group with sum=a[0]. Now, if a[0]+a[1]<=x it is obviously better to put a[1] into that group too, instead of creating the next group.
So we create new groups whenever the sum of the current group is to big.
I have got it. Thank you
I am confused about the samples of this problem Why we can't divide the array as `` [2 , 5] [3 , 4] [7].
In this way the maximum sum in a subarray will be 7 .
That changes the order of the array. Subarrays are contiguous segments of the array, not arbitrary sub sequences.