### Tkm_algo's blog

By Tkm_algo, history, 18 months ago,

Hi, I can't solve this problem for 3 days now. Please help me solve this problem: Two arrays of the same length (n) are given. Need to find any segment so that the sum of the elements of the first array on this segment is equal to the sum of the elements of the second array on this segment. Need to solve in O(n).

• 0

 » 18 months ago, # |   0 Not completely sure if this will work:- SpoilerCreate a new array C of size n, and initialize C[i] = A[i] — B[i], where A and B are the two given arrays. Then the problem boils down to finding a segment in C whose sum is equal to 0. This is a standard problem which can be solved efficiently in O(n) or O(nlogn) using map.
•  » » 18 months ago, # ^ |   0 Thank you very much for help
 » 18 months ago, # | ← Rev. 2 →   0 Hint1Try representing Sum(L, R) in terms of Prefix Sums Hint2We want to make Sum(L, R) equal for both arrays, Can we rearrange the equations to solve this problem? ExplanationUsing, Sum(L, R) = Prefix[R] - Prefix[L] + Arr[L] We want to check, there is any[L, R] such that: Sum1(L, R) = Sum2(L, R) Sum1(L, R) = Sum2(L, R) Prefix1[R] - Prefix1[L] + Arr1[L] = Prefix2[R] - Prefix2[L] + Arr2[L] (Prefix1[R] - Prefix2[R]) = (Prefix1[L] - Arr1[L]) - (Prefix2[L] - Arr2[L]) Let f(L) = (Prefix1[L] - Arr1[L]) - (Prefix2[L] - Arr2[L]) So, the above eqn becomes: (Prefix1[R] - Prefix2[R]) = f(L) => For every R, we can check, is there any f(L) = (Prefix1[R] - Prefix2[R])  Codeint prefix_sum1 = 0; int prefix_sum2 = 0; auto f = [ & ](int L) { return (prefix_sum1 - arr1[L]) - (prefix_sum2 - arr2[L]); }; unordered_set < int > seen; for (int R = 0; R < n; ++R) { prefix_sum1 += arr1[R]; prefix_sum2 += arr2[R]; seen.insert(f(R)); if (seen.count(prefix_sum1 - prefix_sum2)) { return true; } } 
•  » » 18 months ago, # ^ |   0 Thank you very much for your solution