Построить массив из его парного произведения

Опубликовано: 12 Января, 2022

Для массива pair [] , который является парным продуктом, задача состоит в том, чтобы найти исходный массив. Массив парных произведений для массива arr [] - это массив, который содержит произведение всех пар в упорядоченном виде, то есть {(arr [0] * arr [1]), (arr [0] * arr [2]), …, (Arr [1] * arr [2]), (arr [1] * arr [3]),…, (arr [n - 2] * arr [n - 1])} .

Примеры:

Input: pair[] = {2, 3, 6}
Output: 1 2 3
Input: pair[] = {48, 18, 24, 24, 32, 12}
Output: 6 8 3 4

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: сначала найдите размер требуемого массива из заданного массива пар-продукт. Предполагая, что размер исходного массива равен N, а размер массива пар-произведение равен X. Следовательно, решая (N * (N - 1)) / 2 = X , значение N можно вычислить как N = (1 + (int) sqrt (1 + 8 * X)) / 2 .
Теперь давайте посмотрим на решение на примере, допустим, массив парных произведений [A, B, C, D] будет arr [AB, AC, AD, BC, BD, CD], а затем, взяв sqrt ((arr [0 ] * arr [1]) / arr [n - 1]) -> sqrt ((AB * AC) / BC) даст значение A.
После восстановления значения первого элемента все оставшиеся элементы массива пара-продукт могут быть разделены им, чтобы получить оставшиеся элементы исходного массива.

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 array
void 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 array
void 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 code
int 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 approach
class GFG
{
  
// Utility function to print the array
static 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 array
static 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 code
public 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 approach
using System;
      
class GFG
{
  
// Utility function to print the array
static 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 array
static 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 code
public 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

Output:

6 8 3 4

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Структуры данных

Построить массив из его парного произведения

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C++

Java

Python3

C#

РЕКОМЕНДУЕМЫЕ СТАТЬИ