Ethos Software Engineer Interview Experience — Online Assessment on Recoverable Elements from Range-Sum Queries

Recoverable Elements from Range-Sum Queries

You are given an unknown integer array A of length N, with elements indexed from 1 to N.
You will receive Q range-sum queries. Each query contains two integers L and R, and gives you the sum of all elements of A from index L to index R.
Your task is to use the given query information to find all the elements A[i] whose exact value can be uniquely determined. If the value of an element A[i] can be uniquely computed from the given range sums, it is called recoverable.

Input and output requirements:

1. The first line of input contains two integers N and Q, the array length and the number of queries.
2. The next Q lines each contain two integers L and R, representing one known range sum.
3. Output all 1-based element indices i whose values can be uniquely determined, in ascending order, separated by spaces.
4. If no element can be uniquely determined, output -1.

Constraints:

1. 1 <= N <= 10^5
2. 1 <= Q <= 10^5
3. 1 <= L <= R <= N