Given a pair-product array pair[], the task is to find the original array. A pair-product array for an array arr[] is the array that contains product of all the pairs in ordered form i.e. {(arr[0] * arr[1]), (arr[0] * arr[2]), …, (arr[1] * arr[2]), (arr[1] * arr[3]), …, (arr[n – 2] * arr[n – 1])}.
Examples:
Input: pair[] = {2, 3, 6}
Output: 1 2 3
Input: pair[] = {48, 18, 24, 24, 32, 12}
Output: 6 8 3 4
Approach: First find the size of the required array from the given pair-product array. Assuming the size of the original array to be N and size of the pair-product array be X. Therefore, by solving (N * (N – 1)) / 2 = X, the value of N can be calculated as N = (1 + (int)sqrt(1 + 8 * X)) / 2.
Now lets see the solution with an example, lets say the pair-product array of [A, B, C, D] be arr[AB, AC, AD, BC, BD, CD] then by taking sqrt((arr[0] * arr[1]) / arr[n – 1]) -> sqrt((AB * AC) / BC) will give the value A.
Once the value of the first element has been recovered then all the remaining elements of the pair-product array can be divided by it to get the remaining elements of the original array.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>#include <math.h>using namespace std;// Utility function to print the arrayvoid printArr(int arr[], int n){ for (int i = 0; i < n; i++) cout << arr[i] << " ";}// Function to generate the original// array from the pair-product arrayvoid constructArr(int pair[], int n){ int size = (1 + (int)sqrt(1 + 8 * n)) / 2; int arr[size]; // First element of the resulting array arr[0] = sqrt((pair[0] * pair[1]) / pair[size - 1]); // Find all the other elements for (int i = 1; i < size; i++) arr[i] = pair[i - 1] / arr[0]; // Print the elements of the generated array printArr(arr, size);}// Driver codeint main(){ int pair[] = { 48, 18, 24, 24, 32, 12 }; int n = sizeof(pair) / sizeof(int); constructArr(pair, n); return 0;} |
Java
// Java implementation of the approachclass GFG{// Utility function to print the arraystatic void printArr(int arr[], int n){ for (int i = 0; i < n; i++) System.out.print(arr[i] + " ");}// Function to generate the original// array from the pair-product arraystatic void constructArr(int pair[], int n){ int size = (1 + (int)Math.sqrt(1 + 8 * n)) / 2; int []arr = new int[size]; // First element of the resulting array arr[0] = (int) Math.sqrt((pair[0] * pair[1]) / pair[size - 1]); // Find all the other elements for (int i = 1; i < size; i++) arr[i] = pair[i - 1] / arr[0]; // Print the elements of the generated array printArr(arr, size);}// Driver codepublic static void main(String[] args) { int pair[] = { 48, 18, 24, 24, 32, 12 }; int n = pair.length; constructArr(pair, n);}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approach from math import sqrt# Utility function to print the array def printArr(arr, n) : for i in range(n) : print(arr[i], end = " "); # Function to generate the original # array from the pair-product array def constructArr(pair, n) : size = int((1 + sqrt(1 + 8 * n)) // 2); arr = [0] * (size); # First element of the resulting array arr[0] = int(sqrt((pair[0] * pair[1]) / pair[size - 1])); # Find all the other elements for i in range(1, size) : arr[i] = pair[i - 1] // arr[0]; # Print the elements of the generated array printArr(arr, size); # Driver code if __name__ == "__main__" : pair = [ 48, 18, 24, 24, 32, 12 ]; n = len(pair); constructArr(pair, n); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System; class GFG{// Utility function to print the arraystatic void printArr(int []arr, int n){ for (int i = 0; i < n; i++) Console.Write(arr[i] + " ");}// Function to generate the original// array from the pair-product arraystatic void constructArr(int []pair, int n){ int size = (1 + (int)Math.Sqrt(1 + 8 * n)) / 2; int []arr = new int[size]; // First element of the resulting array arr[0] = (int) Math.Sqrt((pair[0] * pair[1]) / pair[size - 1]); // Find all the other elements for (int i = 1; i < size; i++) arr[i] = pair[i - 1] / arr[0]; // Print the elements of the generated array printArr(arr, size);}// Driver codepublic static void Main(String[] args) { int []pair = { 48, 18, 24, 24, 32, 12 }; int n = pair.Length; constructArr(pair, n);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript implementation of the approach// Utility function to print the arrayfunction printArr(arr, n) { for (let i = 0; i < n; i++) document.write(arr[i] + " ");}// Function to generate the original// array from the pair-product arrayfunction constructArr(pair, n) { let size = Math.floor((1 + Math.sqrt(1 + 8 * n)) / 2); let arr = new Array(size); // First element of the resulting array arr[0] = Math.floor(Math.sqrt((pair[0] * pair[1]) / pair[size - 1])); // Find all the other elements for (let i = 1; i < size; i++) arr[i] = Math.floor(pair[i - 1] / arr[0]); // Print the elements of the generated array printArr(arr, size);}// Driver codelet pair = [48, 18, 24, 24, 32, 12];let n = pair.length;constructArr(pair, n);</script> |
6 8 3 4
Time Complexity: O(N).
Auxiliary Space: O(N).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!