Given an array A and m queries

user_7804221 0
Viewed 440

Given an array A and m queries each query is integer T

For each query find index i and j such that

| (|sum of elements from i to j| - T) |

is minimum

wher |x| is abs(x) and array can have negative numbers as well

I was asked this question in directi interview. I had the solution of finding all possible sum and store their indices and sort.

so there will be n*n sums possible.

That would take O(n* n* log(n*n))

now for each query binary search T .That would be O(m* log(n*n))

But he asked to optimize it.I didnt clear the round.

Can anyone give hint for this?

minimum binary-search query-optimization sorting algorithm
2 Answers

If we sort the partial sums, for example,

A  = [2, -4,  6, -3,  9]
ps = [2, -2,  4,  1, 10]

sorted = [-2, 1, 2, 4, 10]

the minimum absolute value of the sum represents the smallest difference between partial sums; in this case, 1 and 2, representing a sum of:

-4 + 6 - 3 = -1

Since we'd like to minimise yet another absolute value of a sum, we want to find the absolute sum difference that's closest to T. I could not find a reference for finding a pair with closest difference to a constant in less than O(n) time, so as is, this approach does not seem better than O(n * log n + n * m). Perhaps we can take advantage of hashing or sorting the queries first since queries that are close to each other represent close ranges during our search, but I'm not sure how.

user_20347870

EDIT: I suppose that solving all sums is actually tremendous wasted work. It is interesting only if m >> n. Else here is my solution.

Imagine a race between the Hare and the Tortoise. I hope you know this story... So the Hare "i" lets the Tortoise "j" going first. He knows he is faster and that he can do a nap. He worries only if the Tortoise is out of sight, "T" meters farther, then he runs very fast until he sees the Tortoise and sleep again... And so on.

So initialization

i = 0
j = 0
bestval = inf
index = none
diff = T

Main loop

while(true):
    if diff < 0:
        i++
        diff += A[i] 
    elif j==n:
        break
    else: 
        j++
        diff += A[j]

    # record best distance
    if abs(diff) < bestval:
       bestval = diff
       index = (i, j)

You cannot miss the optimal because you do not extend research in directions increasing abs(diff). It is pointless to go on summing numbers if you already have too much...

So you only do two runs on A with both j and i, once for every T. This should be O(mn). You even can break-off the loop if diff = 0.

user_61494020
Related