# 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, A, . . , A[n-1], then the input array is

{ (A + A), (A + A), . . , (A + A[n-1]),
(A + A), (A + A), . . , (A + 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 = (inp + inp – inp[n-1]) / 2

As per problem constraints,

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

Note that above relation works only when the size of the input array m is more than 2. For m <= 2, we need to seperately 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

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.

Output:

1 2 3 4 5

## Java

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).     (1 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂  