Help. Array Partition

help
1

Hello! I’m having trouble using binary search (after calculating the partial sum) to complete the following problem, specifically the condition of displaying the smallest result. Any hints are appreciated. (I did the brute force approach successfully but I’m really interested in the binary search one)

Let a[1] , a[2] , …, a[n] be a set of strictly positive numbers. Two indices i and j 1 ≤ i < j < n divide the set so that X = a[1] + a[2] + ... + a[i] , Y = a[i+1] + a[i+2] + ... + a[j] and Z = a[j+1] + a[j+2] + ... + a[n] .

Find two indices i and j ,so that max(X,Y,Z) - min(X,Y,Z) is minimum. . If there is more than one solution display the one for which i is the smallest, and if there’s more than one solution with the same ‘i’, display the one where ‘j’ is the smallest.

Example: for input 1 3 4 2 1 2 10 5 8 6 -> the output should be i = 5 and j = 7 . In this caseX = 13 , Y = 15 , Z = 14 . The difference max(X, Y, Z) - min(X, Y, Z) = 15-13 = 2

2

The time complexity of the mentioned solution is O(nlogn).

First of all maintain a prefix array to get the range sum in O(1).
Loop for i from 1 to n - 1, i.e, you are fixing your value of X = pre[i].
for the rest of the range (i + 1 to n), you can binary search for the index j such that the partitions have least difference with respect to their sum.

1 Like