Decode the array constructed from another array

Given an array constructed from another array by taking sum of every distinct pair in it, decode the array to get back the original array elements.


 
If the original array is A[0], A[1], . . , A[n-1], then the input array is


{ (A[0] + A[1]), (A[0] + A[2]), . . , (A[0] + A[n-1]),
  (A[1] + A[2]), (A[1] + A[3]), . . , (A[1] + A[n-1]),
   ..
   ..
   (A[i] + A[i+1]), (A[i] + A[i+2]), . . , (A[i] + A[n-1]),
   ..
   ..
   (A[n-2] + A[n-1]) }

For example,


Input:  { 3, 4, 5, 5, 6, 7 }
Output: { 1, 2, 3, 4 }
 

Input:  { 3, 4, 5, 6, 5, 6, 7, 7, 8, 9 }
Output: { 1, 2, 3, 4, 5 }
 

Input:  { 3 }
Output: { 1, 2 } or { 2, 1 }

 
Input:  { 3, 4, 5 }
Output: { 1, 2, 3 }


 
The idea is to calculate the first element of the original array by using the below relation

    A[0] = (inp[0] + inp[1] – inp[n-1]) / 2

As per problem constraints,

    inp[0] = A[0] + A[1]
    inp[1] = A[0] + A[2]
    inp[n-1] = A[1] + A[2]

Note that above relation works only when the size of the input array m is more than 2. For m <= 2, we need to separately handle the code.
 

Once we know the first element, we can easily derive the remaining elements of original array by using below relation

    A[i] = inp[i-1] – A[0]

 

Note: If m is the size of given array and n is size of the original array, then the relation between m and n is

m = n(n-1)/2 or n2 – n – 2m = 0

Solving above equation, we get

n = (sqrt(8m+1) + 1)/2

Refer this link for proof of correctness of above equation.

 
C++ implementation –
 

Download   Run Code

Output:

1 2 3 4 5

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂