Sudhanshu_Kumar's blog

By Sudhanshu_Kumar, history, 6 days ago, In English,

How to divide a circular array into k group of contiguous element such that difference between maximum sum and minimum sum is minimum. Each group have contiguous element of array. For e.g If the array is as follow. [6 13 10 2] and k=2 then o/p should be 18(6+10+2)-13=5. As array is circular 6,10,2 are contiguous element of array.

For e.g If the array is as follow. [100 92 133 201 34 34 34 94 108] and k=4 then group as follow 208(108,100), 225(92,133), (201), 196(34,34,34,94) so 225-196=29

I was thinking of binary search similar to painter's partition problem, please clarify if the approach is correct.

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

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can u provide a link to the question...

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It was a company question from an online test, which I don't have access now.

»
6 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You can try to maximize the minimum sum of group among different combinations, then the maximum sum of group will be relatively smaller. You can binary search over the minimum sum of group.

UPD: My approach is wrong. Someone please tell a correct approach. Specifically how to group elements in case when array is 20 20 30 100 50 200 and we have divide it in 3 partitions.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve it for simple array?

»
5 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone give the correct approach for this question it seems a good question....

»
4 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Are all the elements non-negative? Also, limits on number of elements will help in deciding what complexity we are looking for!

Here's a solution in O(N^2log(N)) but I'm can't prove that its correct. Just like painter partition problem I've assumed that we'll minimize the maximum sum possible and in the process we are actually minimizing the difference between maximum and minimum since if we minimize the maximum the minimum sum is kinda fixed beacuse total sum is fixed.