Maximizar la cantidad de elementos distintos posibles en una array a partir de la operación dada

Dado un arreglo A[] de tamaño N , la tarea es maximizar el conteo de elementos distintos en el arreglo insertando las diferencias absolutas de los elementos del arreglo existentes.

Ejemplos: 

Entrada: A[] = {1, 2, 3, 5} 
Salida:
Explicación: 
Las posibles diferencias absolutas entre los elementos de la array son: 
(2 – 1) = 1 
(5 – 3) = 2 
(5 – 2) = 3 
(5 – 1) = 4 
Por lo tanto, insertar 4 en la array maximiza el recuento de elementos distintos.
Entrada: A[] = {1, 2, 3, 6} 
Salida: 6  

Enfoque ingenuo: 
genere todos los pares posibles de la array y almacene sus diferencias absolutas en un conjunto . Inserte todos los elementos de la array en el conjunto. El tamaño final del conjunto denota el máximo de elementos distintos que la array puede poseer después de realizar las operaciones dadas. 
Complejidad de tiempo: O(N 2
Espacio auxiliar: O(N)
Enfoque eficiente: 
Siga los pasos a continuación para optimizar el enfoque anterior:  

  1. Encuentre el elemento máximo de la array. La diferencia absoluta máxima posible de dos elementos cualesquiera no excede el elemento máximo de la array. 
     
  2. Calcula el MCD de la array , ya que es el factor común de toda la array. 
     
  3. Divide el elemento máximo con el gcd de la array para obtener el recuento de los distintos elementos. 
     

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

C++

// C++ program to find the maximum
// possible distinct elements that
// can be obtained from the array
// by performing the given operations
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the gcd
// of two numbers
int gcd(int x, int y)
{
    if (x == 0)
        return y;
    return gcd(y % x, x);
}
 
// Function to calculate and return
// the count of maximum possible
// distinct elements in the array
int findDistinct(int arr[], int n)
{
    // Find the maximum element
    int maximum = *max_element(arr,
                               arr + n);
 
    // Base Case
    if (n == 1)
        return 1;
 
    if (n == 2) {
        return (maximum / gcd(arr[0],
                              arr[1]));
    }
 
    // Finding the gcd of first
    // two element
    int k = gcd(arr[0], arr[1]);
 
    // Calculate Gcd of the array
    for (int i = 2; i < n; i++) {
        k = gcd(k, arr[i]);
    }
 
    // Return the total count
    // of distinct elements
    return (maximum / k);
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << findDistinct(arr, n);
    return 0;
}

Java

// Java program to find the maximum
// possible distinct elements that
// can be obtained from the array
// by performing the given operations
import java.util.*;
 
class GFG{
     
// Function to find the gcd
// of two numbers
static int gcd(int x, int y)
{
    if (x == 0)
        return y;
    return gcd(y % x, x);
}
 
// Function to calculate and return
// the count of maximum possible
// distinct elements in the array
static int findDistinct(int arr[], int n)
{
     
    // Find the maximum element
    int maximum = Arrays.stream(arr).max().getAsInt();
 
    // Base Case
    if (n == 1)
        return 1;
 
    if (n == 2)
    {
        return (maximum / gcd(arr[0],
                              arr[1]));
    }
 
    // Finding the gcd of first
    // two element
    int k = gcd(arr[0], arr[1]);
 
    // Calculate Gcd of the array
    for(int i = 2; i < n; i++)
    {
        k = gcd(k, arr[i]);
    }
 
    // Return the total count
    // of distinct elements
    return (maximum / k);
}
 
// Driver code
public static void main (String[] args)
{
    int arr[] = { 1, 2, 3, 5 };
    int n = arr.length;
 
    System.out.println(findDistinct(arr, n));
}
}
 
// This code is contributed by offbeat

Python3

# Python3 program to find the maximum
# possible distinct elements that
# can be obtained from the array
# by performing the given operations
 
# Function to find the gcd
# of two numbers
def gcd(x, y):
     
    if (x == 0):
        return y
    return gcd(y % x, x)
 
# Function to calculate and return
# the count of maximum possible
# distinct elements in the array
def findDistinct(arr, n):
     
    # Find the maximum element
    maximum = max(arr)
     
    # Base Case
    if (n == 1):
        return 1
 
    if (n == 2):
        return (maximum // gcd(arr[0],
                               arr[1]))
 
    # Finding the gcd of first
    # two element
    k = gcd(arr[0], arr[1])
 
    # Calculate Gcd of the array
    for i in range(2, n):
        k = gcd(k, arr[i])
 
    # Return the total count
    # of distinct elements
    return (maximum // k)
 
# Driver Code
if __name__ == '__main__':
 
    arr = [ 1, 2, 3, 5 ]
    n = len(arr)
 
    print(findDistinct(arr, n))
 
# This code is contributed by mohit kumar 29

C#

// C# program to find the maximum
// possible distinct elements that
// can be obtained from the array
// by performing the given operations
using System;
using System.Linq;
class GFG{
 
// Function to find the gcd
// of two numbers
static int gcd(int x, int y)
{
    if (x == 0)
        return y;
    return gcd(y % x, x);
}
 
// Function to calculate and return
// the count of maximum possible
// distinct elements in the array
static int findDistinct(int []arr, int n)
{
    // Find the maximum element
    int maximum = arr.Max();
 
    // Base Case
    if (n == 1)
        return 1;
 
    if (n == 2)
    {
        return (maximum / gcd(arr[0],
                              arr[1]));
    }
 
    // Finding the gcd of first
    // two element
    int k = gcd(arr[0], arr[1]);
 
    // Calculate Gcd of the array
    for (int i = 2; i < n; i++)
    {
        k = gcd(k, arr[i]);
    }
 
    // Return the total count
    // of distinct elements
    return (maximum / k);
}
 
// Driver Code
public static void Main()
{
    int []arr = { 1, 2, 3, 5 };
    int n = arr.Length;
 
    Console.Write(findDistinct(arr, n));
}
}
 
// This code is contributed by Code_Mech

Javascript

<script>
 
// Javascript program to find the maximum
// possible distinct elements that
// can be obtained from the array
// by performing the given operations
 
// Function to find the gcd
// of two numbers
function gcd(x, y)
{
    if (x == 0)
        return y;
    return gcd(y % x, x);
}
   
// Function to calculate and return
// the count of maximum possible
// distinct elements in the array
function findDistinct(arr, n)
{
       
    // Find the maximum element
    let maximum = Math.max(...arr);
   
    // Base Case
    if (n == 1)
        return 1;
   
    if (n == 2)
    {
        return (maximum / gcd(arr[0],
                              arr[1]));
    }
   
    // Finding the gcd of first
    // two element
    let k = gcd(arr[0], arr[1]);
   
    // Calculate Gcd of the array
    for(let i = 2; i < n; i++)
    {
        k = gcd(k, arr[i]);
    }
   
    // Return the total count
    // of distinct elements
    return (maximum / k);
}
 
// Driver Code
     
    let arr = [ 1, 2, 3, 5 ];
    let n = arr.length;
   
    document.write(findDistinct(arr, n));
 
</script>
Producción: 

5

 

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)
 

Publicación traducida automáticamente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *