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.
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.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
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] \lt = K$$$, which is $$$prefix[j_{lowerBound}] \lt = K + prefix[i - 1]$$$
$$$prefix[j_{upperBound}] - prefix[i - 1] \gt K$$$, which is
$$$prefix[j_{upperBound}] \gt K + prefix[i - 1]$$$
Overall we have, two indices for j that we can use
$$$prefix[j_{lowerBound}] \lt = K + prefix[i - 1] \lt 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.
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.
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. :)
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
UPD this reason does not work as it was pointed out by fast-fourier-transfem 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 arraya[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 indicesi <= jsuch thata[i] + ... + a[j] == 0exist if and only ifb[i] == b[j + 1].Now consider
a[1..n]as constructed before andK := |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 isK, we can answer yes/no to the instanceb[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
Nand 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.
:)