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 arrayvoid 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 functionint 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 approachclass 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 arraydef 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 functionarr= [ 2, 6, 8, 10 ]N = len(arr)# Call the functionfindOriginal(arr, N)# This code is contributed by ihritik |
C#
// C# program for above approachusing 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 arrayfunction 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 codevar arr = [ 2, 6, 8, 10 ];var N = arr.length;// Call the functionfindOriginal(arr, N);// This code is contributed by AnkThon</script> |
Output
2 10 12 16
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
