Find original array from a given encrypted array of size n. Encrypted array is obtained by replacing each element of the original array by the sum of the remaining array elements.
Examples :
Input : arr[] = {10, 14, 12, 13, 11} Output : {5, 1, 3, 2, 4} Original array {5, 1, 3, 2, 4} Encrypted array is obtained as: = {1+3+2+4, 5+3+2+4, 5+1+2+4, 5+1+3+4, 5+1+3+2} = {10, 14, 12, 13, 11} Each element of original array is replaced by the sum of the remaining array elements. Input : arr[] = {95, 107, 103, 88, 110, 87} Output : {23, 11, 15, 30, 8, 31}
Approach is purely based on arithmetic observations which are illustrated below:
Let n = 4, and the original array be ori[] = {a, b, c, d} encrypted array is given as: arr[] = {b+c+d, a+c+d, a+b+d, a+b+c} Elements of encrypted array are : arr[0] = (b+c+d), arr[1] = (a+c+d), arr[2] = (a+b+d), arr[3] = (a+b+c) add up all the elements sum = arr[0] + arr[1] + arr[2] + arr[3] = (b+c+d) + (a+c+d) + (a+b+d) + (a+b+c) = 3(a+b+c+d) Sum of elements of ori[] = sum / n-1 = sum/3 = (a+b+c+d) Thus, for a given encrypted array arr[] of size n, the sum of the elements of the original array ori[] can be calculated as: sum = (arr[0]+arr[1]+....+arr[n-1]) / (n-1) Then, elements of ori[] are calculated as: ori[0] = sum - arr[0] ori[1] = sum - arr[1] . . ori[n-1] = sum - arr[n-1]
Below is the implementation of above steps.
# Python 3 implementation to find # original array from the encrypted # array # Finds and prints the elements of # the original array def findAndPrintOriginalArray(arr, n): # total sum of elements # of encrypted array arr_sum = 0 for i in range(0, n): arr_sum += arr[i] # total sum of elements # of original array arr_sum = int(arr_sum / (n - 1)) # calculating and displaying # elements of original array for i in range(0, n): print((arr_sum - arr[i]), end = " ") # Driver program to test above arr = [10, 14, 12, 13, 11] n = len(arr) findAndPrintOriginalArray(arr, n) # This code is contributed By Smitha
Output :
5 1 3 2 4
Time complexity: O(N)
Auxiliary Space: O(1)