**Given an array of n elements and an integer K, the task is to find the subarray with minimum value of ||a[i] + a[i + 1] + ……. a[j]| – K|. Array may contain negative values. N<=1e5.**

# | User | Rating |
---|---|---|

1 | Benq | 3813 |

2 | tourist | 3768 |

3 | maroonrk | 3570 |

4 | Radewoosh | 3535 |

5 | fantasy | 3526 |

6 | jiangly | 3523 |

7 | Um_nik | 3522 |

8 | orzdevinwang | 3441 |

9 | cnnfls_csy | 3427 |

10 | zh0ukangyang | 3423 |

# | User | Contrib. |
---|---|---|

1 | awoo | 180 |

2 | -is-this-fft- | 178 |

3 | nor | 169 |

4 | Um_nik | 168 |

5 | SecondThread | 164 |

6 | maroonrk | 163 |

6 | adamant | 163 |

8 | kostka | 161 |

9 | YouKn0wWho | 158 |

10 | antontrygubO_o | 155 |

**Given an array of n elements and an integer K, the task is to find the subarray with minimum value of ||a[i] + a[i + 1] + ……. a[j]| – K|. Array may contain negative values. N<=1e5.**

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/29/2023 18:04:31 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

May solve it in $$$O(NlogN)$$$ time. Record all prefix sums in a sorted array. When scanning $$$j$$$, using binary search to find the max prefix sum $$$\leq \sum\limits_{t=1}^j a_t- K$$$ and min prefix sum $$$\geq \sum\limits_{t=1}^j a_t- K$$$. After a binary search, put $$$j$$$ into the sorted array.

Your formula be wrong it should be +K instead of -K

Fix j and scan i, how is it +K? My formula is correct.

Your formula implies you are searching i for j on the right side i.e i <= j. Then for all possible subarray [j >= i] You deduct prefix[j] — prefix[i — 1] to get the actual subarray values and after that search in that array, we want to find two indexes for j, one is $$$j_{lowerBound}$$$ and another is $$$j_{upperBound}$$$, the definitions for lower bound and upper bound as per binary search,

$$$prefix[j_{lowerBound}] - prefix[i - 1] <= K$$$, which is $$$prefix[j_{lowerBound}] <= K + prefix[i - 1]$$$

$$$prefix[j_{upperBound}] - prefix[i - 1] > K$$$, which is

$$$prefix[j_{upperBound}] > K + prefix[i - 1]$$$

Overall we have, two indices for j that we can use

$$$prefix[j_{lowerBound}] <= K + prefix[i - 1] < prefix[j_{upperBound}]$$$

i.e. in a nutshell, loop over all i, find the best possible j on the right side of i, there can be 4 at max, then use them to optimize the answer.Note, there is another case where we have to flip the K when the subarray sums are negative, these is only for subarrays that are positive, for the negative we transform K into $$$prefix[i - 1] - K$$$. We have to handle negative subarrays and positive subarrays differently as there is also absolute inside the sub array.

I think just finding the max and min prefix sums (ignoring the further condition you mentioned) would work (for a fixed $$$j$$$), lets say value of max prefix sum is $$$M$$$ and for min is $$$m$$$. Then, just calculate $$$max( |M-K| , |m-K| )$$$, and update the answer.

This works because the optimal prefix sum must be either max or min for every $$$j$$$.

Bro, we are finding minimum value, why you take max

Oh sorry, I didn't read the question properly.

Can you elaborate your approach a bit more clearly if it works in O(n). That would be helpful.

From where you take this problem? I want to attack it give me link please.

It's an Interview question! He also gave O(nlogn) solution per query but the interviewer insisited on optimising to O(n).

@KartikArya, lol I wonder how much salary they offer, they ask these questions as if they are going to be crunching number day in day out and giving them thousands of dollars of salary. I bet they slack / gossip 80% of the time in their job. Those interviewers should be locked in jail that are torturing youngsters with hard questions that have no solution for.e.g no O(n) solution as someone mentioned.

That's why I keep dreaming of the day when these interviewers are made jobless by Artificial Intelligence.

Lol..that might be true. He gave a hint about using prefix sum (as precomputation) but I don't know how that would optimise the time complexity. Before ending the interview he said that give it some thought you will reach to the solution..lol

Brother, cool down the violence, the problem did nothing wrong

no, i am going to destroy any problem that tries to attack me, i utterly demolish anything that challenge me. :)

insert prefix sums into a set and while calculating current find the largest sum that was previously calculated (last element of the set)

That too would be O(nlogn).

For $$$O(n)$$$, you might use the sliding window trick. Maintain $$$2$$$ pointers: left pointer $$$l$$$ and right pointer $$$r$$$. If sum $$$\geq K$$$, $$$++l$$$, otherwise $$$++r$$$.

That won't work because the array could have negative values

So is there any approach for O(n) solution sir!

UPD this reason does not work as it was pointed out by One in comments

It is not possible in $$$O(n)$$$. Proof by reduction from Element distinctness problem. Consider an instance of Element distinctness problem array

`b[1..n+1]`

. Construct array`a[1..n]`

in a following way:`a[1] = b[2] - b[1]`

,`a[2] = b[3] - b[2]`

,`a[3] = b[4] - b[3]`

, ...,`a[n] = b[n + 1] - b[n]`

. Notice that due to terms cancellation, pair of indices`i <= j`

such that`a[i] + ... + a[j] == 0`

exist if and only if`b[i] == b[j + 1]`

.Now consider

`a[1..n]`

as constructed before and`K := |a[1]| + |a[2]| + ... + |a[n]| + 1`

. Then it is not hard to see that`||a[i] + ... + a[j]| - K|`

minimized when subarray sum is close to zero as possible. So by checking whether answer is`K`

, we can answer yes/no to the instance`b[1..n+1]`

of the Element distinctness problem.Credit to Lewin's answer in this post

This is intelligent, transforming a problem into another problem that has no better solution. Just like all NP-hard problems being compatible with each other.

The element distinctness problem only applies for comparison sorts. Edit- Actually, this reduces to 2SUM and you can use a hash table to do this.

Agree. Indeed Element Distinctness problem in case of integers could be easily solved by creating lookup table of size

`N`

and marking numbers we already met.Still finding closest to zero subarray sum would be useful for this problem

Actually I kinda misread the problem, this reduces to 2SUM and you can use a hash table to do this.

Can you elaborate your approach sir that would be useful.

There is no normal computer algorithm for this problem as some red coder mentioned that if we solve this O(N) we also solve another problem in O(N) which has been proved impossible(hash is not O(1)).

Since there are quantum algorithms for https://en.wikipedia.org/wiki/Element_distinctness_problem,

may be there is a quantum computer algorithm as wikipedia says. So, its time for some quantum competitive programming my boi.

Its time to make the leap from these boring for loops and play with superpositions in quantum space.

:)