jmdons's blog

By jmdons, history, 4 weeks ago, In English,

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!

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please provide an explanation to this solution ?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh yes. I missed this case. Thank you !

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.