### Sudhanshu_Kumar's blog

By Sudhanshu_Kumar, history, 8 months ago, ,

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.

• +7

 » 8 months ago, # |   0 Can u provide a link to the question...
•  » » 8 months ago, # ^ |   0 It was a company question from an online test, which I don't have access now.
 » 8 months ago, # | ← Rev. 2 →   0 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.
•  » » 8 months ago, # ^ |   0 can u give proof for this solution??
 » 8 months ago, # |   0 How to solve it for simple array?
 » 8 months ago, # |   +3 Can someone give the correct approach for this question it seems a good question....
 » 8 months ago, # | ← Rev. 3 →   0 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.