Find the indices of the array which can be determined, given q range sums in the form of [L, R]

Revision en3, by eleganc, 2022-10-05 17:50:41

Hi, I faced this question in a recent mock assessment. I cannot think of any approach to solve this. Ideas are welcomed. Problem: A new method has to be derived for decrypting secret codes. THere is a secret array arr of length n, along with a 2D array query with dimension m*2, where each row denotes a pair (L, R) which denotes the sum arr[L] + arr[L+1] + .... + arr[R]. The goal is to determine all the indices of arr whose value can be identified.

Eg. n = 4 query = [[1, 3], [1, 2], [4, 4]]

First query gives the value of arr + arr + arr. The second query gives the value of arr+ arr. Third query gives the value of arr directly.

Using the above only index 3 and 4 can be determined (1 based indexing). So ans = [3, 4].

Constraints: 1 <= n <= 1e5; 1 <= m <= 1e5; 1 <= l <= r <= n #### History

Revisions Rev. Lang. By When Δ Comment
en3 eleganc 2022-10-05 17:50:41 2 Tiny change: 'n <= 1e5\n1 <= m <= 1e5\n1 <= l <' -> 'n <= 1e5\n\n1 <= m <= 1e5\n\n1 <= l <'
en2 eleganc 2022-10-05 17:49:09 697
en1 eleganc 2022-10-05 17:42:02 217 Initial revision (published)