Sudhanshu_Kumar's blog

Need help with a binary search question
By Sudhanshu_Kumar, history, 5 years 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

Comments Comments (5)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can u provide a link to the question...

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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.

→ Reply
»
5 years 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....

→ Reply