Given an array arr[] of length N, the task is to find the original array such that every ith element in the given array(arr[i]) is the average value of the first i elements of the original array.
Examples:
Input: arr = {4 3 3 3}
Output: 4 2 3 3
Explanation: (4) / 1 = 1, (4+2) / 2 = 3, (4+2+3) / 3 = 3, (4+2+3+3) / 4 = 3Input: arr = {2 6 8 10}
Output: 2 10 12 16
Explanation: (2) / 1 = 2, (2+10) / 2 = 6, (2+10+12) / 3 = 8, (2+10+12+16) / 4 = 10
Approach: The given problem can be solved using a mathematical approach. Follow the steps below:
- Initialize a variable sum to the first element of the array arr
- Iterate the array arr from 2nd index till the end and at every iteration:
- Multiply current element arr[i] with current index + 1 (i + 1) and subtract the value of sum from it
- Add the resulting current element to the variable sum
- Return the resulting array after modification as it will be the original array
C++
// C++ implementation for the above approach #include <iostream> using namespace std; // Function to find the original // array from the modified array void findOriginal( int arr[], int N) { // Initialize the variable sum // with the first element of array int sum = arr[0]; for ( int i = 1; i < N; i++) { // Calculate original element // from average of first i elements arr[i] = (i + 1) * arr[i] - sum; // Add current element to sum sum += arr[i]; } // Print the array for ( int i = 0; i < N; i++) { cout << arr[i] << " " ; } } // Driver function int main() { int arr[] = { 2, 6, 8, 10 }; int N = sizeof (arr) / sizeof (arr[0]); // Call the function findOriginal(arr, N); return 0; } |
Java
// Java implementation for the above approach class GFG { // Function to find the original // array from the modified array static void findOriginal( int arr[], int N) { // Initialize the variable sum // with the first element of array int sum = arr[ 0 ]; for ( int i = 1 ; i < N; i++) { // Calculate original element // from average of first i elements arr[i] = (i + 1 ) * arr[i] - sum; // Add current element to sum sum += arr[i]; } // Print the array for ( int i = 0 ; i < N; i++) { System.out.print(arr[i] + " " ); } } // Driver function public static void main(String [] args) { int [] arr = new int [] { 2 , 6 , 8 , 10 }; int N = arr.length; // Call the function findOriginal(arr, N); } } // This code is contributed by ihritik |
Python3
# Python implementation for the above approach # Function to find the original # array from the modified array def findOriginal(arr, N): # Initialize the variable sum # with the first element of array sum = arr[ 0 ] for i in range ( 1 , N): # Calculate original element # from average of first i elements arr[i] = (i + 1 ) * arr[i] - sum # Add current element to sum sum = sum + arr[i] # Print the array for i in range ( 0 , N): print (arr[i], end = " " ) # Driver function arr = [ 2 , 6 , 8 , 10 ] N = len (arr) # Call the function findOriginal(arr, N) # This code is contributed by ihritik |
C#
// C# program for above approach using System; class GFG { // Function to find the original // array from the modified array static void findOriginal( int [] arr, int N) { // Initialize the variable sum // with the first element of array int sum = arr[0]; for ( int i = 1; i < N; i++) { // Calculate original element // from average of first i elements arr[i] = (i + 1) * arr[i] - sum; // Add current element to sum sum += arr[i]; } // Print the array for ( int i = 0; i < N; i++) Console.Write(arr[i] + " " ); } // Driver Code public static void Main(String[] args) { int N = 4; int [] arr = { 2, 6, 8, 10 }; findOriginal(arr, N); } } // This code is contributed by dwivediyash |
Javascript
<script> // JavaScript implementation for the above approach // Function to find the original // array from the modified array function findOriginal(arr, N) { // Initialize the variable sum // with the first element of array var sum = arr[0]; for ( var i = 1; i < N; i++) { // Calculate original element // from average of first i elements arr[i] = (i + 1) * arr[i] - sum; // Add current element to sum sum += arr[i]; } // Print the array for ( var i = 0; i < N; i++) { document.write(arr[i] + " " ); } } // Driver code var arr = [ 2, 6, 8, 10 ]; var N = arr.length; // Call the function findOriginal(arr, N); // This code is contributed by AnkThon </script> |
2 10 12 16
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!