Minimizar la longitud de una array que consiste en la diferencia entre todos los pares posibles

Dada una array arr[] de tamaño N , la tarea es encontrar el recuento mínimo de elementos necesarios para insertar en la array de modo que exista la diferencia absoluta de todos los pares posibles en la array.

Ejemplos:

Entrada: arr[] = { 3, 5 }
Salida: 3
Explicación:
Insertar 2 en la array modifica arr[] a { 2, 3, 5 }
Insertar 1 en la array modifica arr[] a { 1, 2, 3, 5 }
Insertar 4 en la array modifica arr[] a { 1, 2, 3, 4, 5 }
Dado que la diferencia absoluta de todos los pares posibles de la array están presentes en la array, la salida requerida es 3.

Entrada: arr[] = { 2, 4 }
Salida: 0
Explicación:
Dado que la diferencia absoluta de todos los arreglos de pares posibles ya está presente en el arreglo, el resultado requerido es 0.

Enfoque ingenuo: el enfoque más simple para resolver este problema es encontrar la diferencia absoluta de cada par posible de la array y verificar si la diferencia obtenida está presente en la array o no . Si no está presente, entonces inserte la diferencia obtenida. De lo contrario, imprima el recuento de elementos insertados en la array.

Complejidad de tiempo: O(N * X), donde X es el elemento máximo de la array.
Espacio Auxiliar: O(X)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:

Dado que la diferencia absoluta de todos los pares posibles de la array final debe estar presente en la array.
Por lo tanto, la array final debe tener la forma de X, 2 * X, 3 * X, 4 * X, …

De la secuencia anterior de la array final, se puede observar que el valor de X debe ser el GCD de la array dada.

Siga los pasos a continuación para resolver el problema:

Atraviese la array y calcule el GCD de la array dada , digamos, X .
Encuentre el elemento más grande de la array , digamos, Max .
El recuento total de elementos en la array al insertar la diferencia absoluta de todos los pares posibles es (Max) / X .
Por lo tanto, el recuento total de elementos insertados en la array es igual a ((Max / X) – N) .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the GCD of an array
int findGcd(int arr[], int N)
{
 
    // Stores GCD of an array
    int gcd = arr[0];
 
    // Traverse the array
    for (int i = 1; i < N; i++) {
 
        // Update gcd
        gcd = __gcd(gcd, arr[i]);
    }
    return gcd;
}
 
// Function to find minimum count of elements
// inserted into the array such that absolute
// difference of pairs present in the array
void findMax(int arr[], int N)
{
 
    // Stores gcd of the array
    int gcd = findGcd(arr, N);
 
    // Stores the largest element
    // in the array
    int Max = INT_MIN;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // Update Max
        Max = max(Max, arr[i]);
    }
 
    // Stores minimum count of elements inserted
    // into the array such that absolute difference
    // of pairs present in the array
    int ans = (Max / gcd) - N;
 
    cout << ans;
}
 
// Driver Code
int main()
{
 
    // Given array
    int arr[] = { 3, 5 };
 
    // Size of the array
    int N = (sizeof(arr) / (sizeof(arr[0])));
 
    // Function Call
    findMax(arr, N);
}

Java

// Java program for the above approach
import java.util.*;
class GFG
{
     
// Recursive function to return gcd of a and b
static int gcdd(int a, int b)
{
    // Everything divides 0
    if (a == 0)
       return b;
    if (b == 0)
       return a;
   
    // base case
    if (a == b)
        return a;
   
    // a is greater
    if (a > b)
        return gcdd(a - b, b);
    return gcdd(a, b - a);
}
       
// Function to find the GCD of an array
static int findGcd(int arr[], int N)
{
 
    // Stores GCD of an array
    int gcd = arr[0];
 
    // Traverse the array
    for (int i = 1; i < N; i++)
    {
 
        // Update gcd
        gcd = gcdd(gcd, arr[i]);
    }
    return gcd;
}
 
// Function to find minimum count of elements
// inserted into the array such that absolute
// difference of pairs present in the array
static void findMax(int arr[], int N)
{
 
    // Stores gcd of the array
    int gcd = findGcd(arr, N);
 
    // Stores the largest element
    // in the array
    int Max = Integer.MIN_VALUE;
 
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
 
        // Update Max
        Max = Math.max(Max, arr[i]);
    }
 
    // Stores minimum count of elements inserted
    // into the array such that absolute difference
    // of pairs present in the array
    int ans = (Max / gcd) - N;
    System.out.println(ans);
}
   
// Driver code
public static void main(String[] args)
{
   
    // Given array
    int arr[] = { 3, 5 };
 
    // Size of the array
    int N = arr.length;
 
    // Function Call
    findMax(arr, N);
}
}
 
// This code is contributed by susmitakundugoaldanga.

Python3

# Python3 program for the above approach
import math
import sys
 
# Function to find the GCD of an array
def findGcd(arr, N):
     
    # Stores GCD of an array
    gcd = arr[0]
     
    # Traverse the array
    for i in range(1, N):
         
        # Update gcd
        gcd = math.gcd(gcd, arr[i])
 
    return gcd
 
# Function to find minimum count of elements
# inserted into the array such that absolute
# difference of pairs present in the array
def findMax(arr, N):
     
    # Stores gcd of the array
    gcd = findGcd(arr, N)
     
    # Stores the largest element
    # in the array
    Max = -sys.maxsize - 1
     
    # Traverse the array
    for i in range(N):
         
        # Update Max
        Max = max(Max, arr[i])
 
    # Stores minimum count of elements inserted
    # into the array such that absolute difference
    # of pairs present in the array
    ans = (Max // gcd) - N
 
    print(ans)
 
# Driver Code
if __name__ == "__main__":
     
    # Given array
    arr = [3, 5]
     
    # Size of the array
    N = len(arr)
 
    # Function Call
    findMax(arr, N)
 
# This code is contributed by chitranayal

C#

// C# program for the above approach
using System;
 
class GFG
{
 
    // Recursive function to return gcd of a and b
    static int gcdd(int a, int b)
    {
       
        // Everything divides 0
        if (a == 0)
            return b;
        if (b == 0)
            return a;
 
        // base case
        if (a == b)
            return a;
 
        // a is greater
        if (a > b)
            return gcdd(a - b, b);
        return gcdd(a, b - a);
    }
 
    // Function to find the GCD of an array
    static int findGcd(int[] arr, int N)
    {
 
        // Stores GCD of an array
        int gcd = arr[0];
 
        // Traverse the array
        for (int i = 1; i < N; i++)
        {
 
            // Update gcd
            gcd = gcdd(gcd, arr[i]);
        }
        return gcd;
    }
 
    // Function to find minimum count of elements
    // inserted into the array such that absolute
    // difference of pairs present in the array
    static void findMax(int[] arr, int N)
    {
 
        // Stores gcd of the array
        int gcd = findGcd(arr, N);
 
        // Stores the largest element
        // in the array
        int Max = Int32.MinValue;
 
        // Traverse the array
        for (int i = 0; i < N; i++)
        {
 
            // Update Max
            Max = Math.Max(Max, arr[i]);
        }
 
        // Stores minimum count of elements inserted
        // into the array such that absolute difference
        // of pairs present in the array
        int ans = (Max / gcd) - N;
        Console.WriteLine(ans);
    }
 
    // Driver code
    static public void Main()
    {
 
        // Given array
        int[] arr = new int[] { 3, 5 };
 
        // Size of the array
        int N = arr.Length;
 
        // Function Call
        findMax(arr, N);
    }
}
 
// This code is contributed by Dharanendra L V.

Javascript

<script>
 
// Javascript program for the above approach
 
// Recursive function to return gcd of a and b
function gcdd(a, b)
{
     
    // Everything divides 0
    if (a == 0)
        return b;
    if (b == 0)
        return a;
 
    // Base case
    if (a == b)
        return a;
 
    // a is greater
    if (a > b)
        return gcdd(a - b, b);
         
    return gcdd(a, b - a);
}
 
// Function to find the GCD of an array
function findGcd(arr, N)
{
     
    // Stores GCD of an array
    var gcd = arr[0];
 
    // Traverse the array
    for(i = 1; i < N; i++)
    {
         
        // Update gcd
        gcd = gcdd(gcd, arr[i]);
    }
    return gcd;
}
 
// Function to find minimum count of elements
// inserted into the array such that absolute
// difference of pairs present in the array
function findMax(arr, N)
{
     
    // Stores gcd of the array
    var gcd = findGcd(arr, N);
 
    // Stores the largest element
    // in the array
    var Max = Number.MIN_VALUE;
 
    // Traverse the array
    for(i = 0; i < N; i++)
    {
         
        // Update Max
        Max = Math.max(Max, arr[i]);
    }
 
    // Stores minimum count of elements inserted
    // into the array such that absolute difference
    // of pairs present in the array
    var ans = (Max / gcd) - N;
    document.write(ans);
}
 
// Driver code
 
// Given array
var arr = [ 3, 5 ];
 
// Size of the array
var N = arr.length;
 
// Function Call
findMax(arr, N);
 
// This code is contributed by umadevi9616
 
</script>

Producción:

Complejidad de tiempo: O(N * Log(X)), donde X es el elemento más grande de la array.
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por prasann7676 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta