Given an array arr[] of length N, where arr is derived from an array nums[] which is lost. Array arr[] is derived as:
arr[i] = (nums[0] + nums[1] + … + nums[i]) + (nums[i] + nums[i+1] + … + nums[N-1]).
The task is to find nums[] array of length N.
Examples:
Input: N = 4, arr[] = {9, 10, 11, 10}
Output: {1, 2, 3, 2}
Explanation: If nums[] = {1, 2, 3, 2}, then according to above definition
arr[0] = (nums[0]) + (nums[0] + nums[1] + nums[2] + nums[3]) = 1 + 1 + 2 + 3 + 2 = 9
arr[1] = (nums[0] + nums[1]) + (nums[1] + nums[2] + nums[3]) = 1 + 2 + 2 + 3 + 2 = 10
arr[2] = (nums[0] + nums[1] + nums[2]) + (nums[2] + nums[3]) = 1 + 2 + 3 + 3 + 2 = 11
arr[3] = (nums[0] + nums[1] + nums[2] + nums[3]) + (nums[3]) = 1 + 2 + 3 + 2 + 2 = 10Input: N = 2, arr[] = [25, 20]
Output: [10, 5]
Approach: Follow the below idea to solve the problem:
Suppose nums[] contains [a1, a2, a3, …, aN]
Then, sum = a1 + a2 + a3 + . . . + aN.
We are given
b1 = a1 + a1 + a2 + . . . + aN = a1 + sum …..(1)
Similarly,
b2 = a1 + a2 + a2 + . . . + aN = a2 + sum …..(2)
. . . (so on) and in last
b1 = a1 + a2 + a3 + . . . + aN + aN = aN + sum …..(N)
where [b1, b2, b3 , . . ., bN] are elements of arr[] and,
total = b1 + b2 + b3 + . . . + bNAdding all equation (1) + (2) + (3) + …. + (N) we will get
b1 + b2 + b3 + . . . + bN = (a1 + sum) + (a2 + sum) + . . . + (aN + sum)
total = (a1 + a1 + a2 + . . . + aN) + (N * sum)
total = (sum) + (N * sum)
total = (N + 1) * sumNow find the value of sum variable after that simply:
a1 = (b1 – sum), a2 = (b2 – sum), . . ., aN = (bN – sum)
Using the above idea follow the below steps to implement the code:
- First of all, try to store the sum of elements of arr[] in a variable let’s say total
- Using the formula (N + 1) * sum = total, we will get the value of variable sum which denotes the sum of elements present in the nums[] array.
- At last traverse N times to find nums[0] = arr[0] – sum, nums[1] = arr[1] – sum and so on.
- Return the array and print it.
Below is the implementation of the above approach:
C++
// C++ Algorithm for the above approach#include <iostream>#include <vector>using namespace std;// Function to find the original// array nums[]vector<int> findOrgArray(vector<int> arr, int N){ // Total variable stores the sum of // elements of arr[] int total = 0; for (int val : arr) total += val; // Sum variable stores the sum of // elements of nums[] int sum = (total / (N + 1)); vector<int> v; // Traversing to find the elements // of nums[] for (int i = 0; i < N; i++) { int val = arr[i] - sum; v.push_back(val); } // Returning nums[] return v;}int main(){ int N = 4; vector<int> arr = { 9, 10, 11, 10 }; vector<int> v = findOrgArray(arr, N); for (auto val : v) cout << val << " "; return 0;} |
Java
// Java algorithm of the above approachimport java.util.*;class GFG { // Driver Code public static void main(String[] args) { int N = 4; int[] arr = { 9, 10, 11, 10 }; List<Integer> nums = findOrgArray(arr, N); for (int x : nums) System.out.print(x + " "); } // Function to find the original // array nums[] public static List<Integer> findOrgArray(int[] arr, int N) { // Total variable stores the sum of // elements of arr[] int total = 0; for (int val : arr) total += val; // Sum variable stores the sum of // elements of nums[] int sum = (total / (N + 1)); List<Integer> nums = new ArrayList<>(); // Traversing to find the elements // of nums[] for (int i = 0; i < N; i++) { int val = arr[i] - sum; nums.add(val); } // Returning nums[] return nums; }} |
Python3
# python3 Algorithm for the above approach # Function to find the original# array nums[]def findOrgArray(arr, N) : # Total variable stores the sum of # elements of arr[] total = 0 for i in arr : total+= i # Sum variable stores the sum of # elements of nums[] sum = int(total / (N + 1)); v = [] # Traversing to find the elements # of nums[] for i in range (N) : val = arr[i] - sum v.append(val) # Returning nums[] return v# Driver Codeif __name__ == "__main__" : N = 4 arr = [ 9, 10, 11, 10 ] v = findOrgArray(arr, N) for val in v : print(val,end=' ')# this code is contributed by aditya942003patil |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to find the original // array nums[] public static List<int> findOrgArray(int[] arr, int N) { // Total variable stores the sum of // elements of arr[] int total = 0; //for (int x = 0; x < arr.count; x++) foreach (int val in arr) total += val; // Sum variable stores the sum of // elements of nums[] int sum = (total / (N + 1)); List<int> nums = new List<int>(); // Traversing to find the elements // of nums[] for (int i = 0; i < N; i++) { int val = arr[i] - sum; nums.Add(val); } // Returning nums[] return nums; } // Driver Code public static void Main(String []args) { int N = 4; int[] arr = { 9, 10, 11, 10 }; List<int> nums = findOrgArray(arr, N); for (int x = 0; x < nums.Count; x++) Console.Write(nums[x] + " "); }}// This code is contributed by sanjoy_62. |
Javascript
<script>// Function to find the original// array nums[]function findOrgArray(arr, N){ // Total variable stores the sum of // elements of arr[] let total = 0; for (let i = 0; i < N; i++) total += arr[i]; // Sum variable stores the sum of // elements of nums[] let sum = (total / (N + 1)); let v= new Array(N); // Traversing to find the elements // of nums[] for (let i = 0; i < N; i++) { v[i] = arr[i] - sum; } // Returning nums[] return v;} let N = 4; let arr = [ 9, 10, 11, 10 ]; let v = findOrgArray(arr, N); for (let i = 0; i < N; i++) document.write(v[i]+ " "); // This code is contributed by satwik4409. </script> |
Output
1 2 3 2
Time Complexity: O(N)
Auxiliary Space: O(N), to further reduce it to O(1), store the value in the same given array arr[] rather than storing it in a new array.
Another Approach:
- Initialize a variable named “total” to 0.
- Traverse the input array “arr” using a range-based for loop.
a. For each element “val” in “arr”, add “val” to the “total” variable. - Compute the sum of the original array “nums” using the formula: sum = total / (N + 1).
- Traverse the input array “arr” again using a for loop with index “i” from 0 to N-1.
a. For each element in “arr”, subtract “sum” from it and store the result back into “arr[i]”. This effectively undoes the modification made to “arr” and recovers the original array “nums”.
Below is the implementation of the above approach:
C++
#include <iostream>#include <vector>using namespace std;// Function to find the original array nums[]void findOrgArray(vector<int>& arr, int N){ // Total variable stores the sum of elements of arr[] int total = 0; for (int val : arr) total += val; // Sum variable stores the sum of elements of nums[] int sum = (total / (N + 1)); // Traversing to find the elements of nums[] for (int i = 0; i < N; i++) { arr[i] = arr[i] - sum; }}int main(){ int N = 4; vector<int> arr = { 9, 10, 11, 10 }; findOrgArray(arr, N); for (auto val : arr) cout << val << " "; return 0;} |
Java
import java.util.*;import java.io.*;public class GFG { // Function to find the original array nums[] static void findOrgArray(List<Integer> arr, int N) { // Total variable stores the sum of elements of arr[] int total = 0; for (int val : arr) { total += val; } // Sum variable stores the sum of elements of nums[] int sum = total / (N + 1); // Traversing to find the elements of nums[] for (int i = 0; i < N; i++) { arr.set(i, arr.get(i) - sum); } } // Driver Code public static void main(String[] args) { int N = 4; List<Integer> arr = new ArrayList<>(); arr.add(9); arr.add(10); arr.add(11); arr.add(10); findOrgArray(arr, N); for (int val : arr) { System.out.print(val + " "); } }} |
Python3
#Function to find the original array nums[]def find_org_array(arr, N): total = 0 #Total variable stores the sum of elements of arr[] for val in arr: total += val #Sum variable stores the sum of elements of nums[] sum = int(total / (N + 1)) #Traversing to find the elements of nums[] for i in range(N): arr[i] -= sum return arr#Driver Codearr=[9, 10, 11, 10]n=4#function callarr=find_org_array(arr,n)for val in arr: print(val,end=" ") |
C#
using System;using System.Collections.Generic;class Program{ // Function to find the original array nums[] static void FindOrgArray(List<int> arr, int N) { // Total variable stores the sum of elements of arr[] int total = 0; foreach (int val in arr) total += val; // Sum variable stores the sum of elements of nums[] int sum = total / (N + 1); // Traversing to find the elements of nums[] for (int i = 0; i < N; i++) { arr[i] = arr[i] - sum; } } static void Main() { int N = 4; List<int> arr = new List<int> { 9, 10, 11, 10 }; FindOrgArray(arr, N); foreach (var val in arr) Console.Write(val + " "); }} |
Javascript
// Function to find the original array nums[]function findOrgArray(arr, N) { // Total variable stores the sum of elements of arr[] let total = 0; for (let val of arr) { total += val; } // Sum variable stores the sum of elements of nums[] let sum = Math.floor(total / (N + 1)); // Traversing to find the elements of nums[] for (let i = 0; i < N; i++) { arr[i] = arr[i] - sum; }}// Driver codelet N = 4;let arr = [9, 10, 11, 10];findOrgArray(arr, N);for (let val of arr) { console.log(val + " ");} |
Output
1 2 3 2
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!
