1

Let there be an array A with n elements. Every element in A has a key, and a weight.

Divide A into 2 subarrays (does not have to be of equal size), where every key in group 1 is smaller than every key in group 2, and the total weight of both subarrays must be equal.

Time Complexity : O(n) in the worst case scenerio.

I've tried using the quick SELECT algorithm and partitioning the array by key values. that gives us 2 subarrays in which every key is subarray 1 is smaller than subarray 2. If weights are not equal, we'll need to move the biggest key element into the other subarray and then compare weights. The issue is, finding biggest key element every time takes n/2 + (n/2)-1... which is O(n^2).

Nati Shen-Gordon
  • 25
  • 5
  • 1
    Instead of moving the biggest key element, you partition the half with the larger sum. The first partition looks at all N value, the second looks at N/2 values, the third looks at N/4, and so on. So the total time is `N + N/2 + N/4 + ...` which is not more than 2N. – user3386109 Jan 24 '23 at 22:17

0 Answers0