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: 5
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:
- 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.
- Calcula el MCD de la array , ya que es el factor común de toda la array.
- 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>
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