Given an array of integers greater[] in which every value of array represents how many elements are greater to its right side in an unknown array arr[]. Our task is to generate original array arr[]. It may be assumed that the original array contains elements in range from 1 to n and all elements are unique
Examples:
Input: greater[] = { 6, 3, 2, 1, 0, 0, 0 }
Output: arr[] = [ 1, 4, 5, 6, 7, 3, 2 ]Input: greater[] = { 0, 0, 0, 0, 0 }
Output: arr[] = [ 5, 4, 3, 2, 1 ]
We consider an array of elements temp[] = {1, 2, 3, 4, .. n}. We know value of greater[0] indicates count of elements greater than arr[0]. We can observe that (n – greater[0])-th element of temp[] can be put at arr[0]. So we put this at arr[0] and remove this from temp[]. We repeat above process for remaining elements. For every element greater[i], we put (n – greater[i] – i)-th element of temp[] in arr[i] and remove it from temp[].
Below is the implementation of the above idea
C++
// C++ program to generate original array // from an array that stores counts of // greater elements on right. #include <bits/stdc++.h> using namespace std; void originalArray( int greater[], int n) { // Array that is used to include every // element only once vector< int > temp; for ( int i = 0; i <= n; i++) temp.push_back(i); // Traverse the array element int arr[n]; for ( int i = 0; i < n; i++) { // find the K-th (n-greater[i]-i) // smallest element in Include_Array int k = n - greater[i] - i; arr[i] = temp[k]; // remove current k-th element // from Include array temp.erase(temp.begin() + k); } // print resultant array for ( int i = 0; i < n; i++) cout << arr[i] << " " ; } // driver program to test above function int main() { int Arr[] = { 6, 3, 2, 1, 0, 1, 0 }; int n = sizeof (Arr) / sizeof (Arr[0]); originalArray(Arr, n); return 0; } |
Java
// Java program to generate original array // from an array that stores counts of // greater elements on right. import java.util.Vector; class GFG { static void originalArray( int greater[], int n) { // Array that is used to include every // element only once Vector<Integer> temp = new Vector<Integer>(); for ( int i = 0 ; i <= n; i++) temp.add(i); // Traverse the array element int arr[] = new int [n]; for ( int i = 0 ; i < n; i++) { // find the K-th (n-greater[i]-i) // smallest element in Include_Array int k = n - greater[i] - i; arr[i] = temp.get(k); // remove current k-th element // from Include array temp.remove(k); } // print resultant array for ( int i = 0 ; i < n; i++) System.out.print(arr[i] + " " ); } // Driver code public static void main(String[] args) { int Arr[] = { 6 , 3 , 2 , 1 , 0 , 1 , 0 }; int n = Arr.length; originalArray(Arr, n); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program original array from an # array that stores counts of greater # elements on right def originalArray(greater, n): # array that is used to include # every element only once temp = [] for i in range (n + 1 ): temp.append(i) # traverse the array element arr = [ 0 for i in range (n)] for i in range (n): # find the Kth (n-greater[i]-i) # smallest element in Include_array k = n - greater[i] - i arr[i] = temp[k] # remove current kth element # from include array del temp[k] for i in range (n): print (arr[i], end = " " ) # Driver code arr = [ 6 , 3 , 2 , 1 , 0 , 1 , 0 ] n = len (arr) originalArray(arr, n) # This code is contributed # by Mohit Kumar |
C#
// C# program to generate original array // from an array that stores counts of // greater elements on right. using System; using System.Collections.Generic; class GFG { static void originalArray( int [] greater, int n) { // Array that is used to include every // element only once List< int > temp = new List< int >(); for ( int i = 0; i <= n; i++) temp.Add(i); // Traverse the array element int [] arr = new int [n]; for ( int i = 0; i < n; i++) { // find the K-th (n-greater[i]-i) // smallest element in Include_Array int k = n - greater[i] - i; arr[i] = temp[k]; // remove current k-th element // from Include array temp.RemoveAt(k); } // print resultant array for ( int i = 0; i < n; i++) Console.Write(arr[i] + " " ); } // Driver code public static void Main() { int [] Arr = { 6, 3, 2, 1, 0, 1, 0 }; int n = Arr.Length; originalArray(Arr, n); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // JavaScript program to generate original array // from an array that stores counts of // greater elements on right. function originalArray(greater,n) { // Array that is used to include every // element only once let temp = []; for (let i = 0; i <= n; i++) temp.push(i); // Traverse the array element let arr = new Array(n); for (let i = 0; i < n; i++) { // find the K-th (n-greater[i]-i) // smallest element in Include_Array let k = n - greater[i] - i; arr[i] = temp[k]; // remove current k-th element // from Include array temp.splice(k,1); } // print resultant array for (let i = 0; i < n; i++) document.write(arr[i] + " " ); } // Driver code let Arr=[6, 3, 2, 1, 0, 1, 0 ]; let n = Arr.length; originalArray(Arr, n); // This code is contributed by patel2127 </script> |
1 4 5 6 7 2 3
Time Complexity: (n2) (Erase operation takes O(n) in vector).
Auxiliary Space: O(n), extra space is required for temp and res arrays.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!