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).
Not completely sure if this will work:-
Create 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.
Thank you very much for help
Try representing Sum(L, R) in terms of Prefix Sums
We want to make Sum(L, R) equal for both arrays, Can we rearrange the equations to solve this problem?
Thank you very much for your solution