Dada una array arr[] de tamaño N , la tarea es maximizar el recuento de distintos elementos de la array insertando repetidamente la diferencia absoluta entre todos los pares posibles de la array dada.
Ejemplos:
Entrada: arr[] = { 2, 4, 16 }
Salida: 9
Explicación:
Insertar (arr[2] – arr[1]) modifica arr[] a { 2, 4, 12, 16 }
Insertar (arr[2] – arr[1]) modifica arr[] a { 2, 4, 8, 12, 16 }
Insertando (arr[2] – arr[1]) modifica arr[] a { 2, 4, 6, 8, 12, 16 }
Insertar (arr[4] – arr[0]) modifica arr[] a { 2, 4, 6, 8, 10, 12, 16 } Insertar (arr[6] – arr[0]) modifica arr[
] a { 2, 4, 6, 8, 10, 12, 14 16 }
Insertar (arr[2] – arr[0]) modifica arr[] a { 2, 4, 4 6, 8, 10, 12, 14 16 }
Insertar (arr[2] – arr[1]) modifica arr[] a { 0, 2, 4, 4 6, 8, 10, 12, 14 16 } Por lo tanto, la salida requerida es 9
.Entrada: arr[] = { 3, 6, 5, 4 }
Salida: 7
Enfoque ingenuo: el enfoque más simple para resolver este problema es seleccionar repetidamente un par de la array dada e insertar la diferencia absoluta de ese par. Finalmente, verifique si la diferencia absoluta de todos los pares posibles ya está presente en la array o no. Si se encuentra que es cierto, imprima el recuento de elementos distintos en la array.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: la idea es utilizar el hecho de que el MCD de dos números se puede obtener restando repetidamente el número más pequeño del número más grande hasta que dos elementos sean iguales. Por lo tanto, inserte los elementos en la array de manera que la diferencia absoluta entre todos los elementos adyacentes sea igual al GCD de la array. Siga los pasos a continuación para resolver el problema:
- Encuentre el elemento más grande de la array, digamos Max .
- Encuentre el GCD de la array, por ejemplo, GCDArr .
- Finalmente, imprima el valor de ((Max / GCDArr) + 1) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the gcd of
// the two numbers
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to find distinct elements in the array
// by repeatidely inserting the absolute difference
// of all possible pairs
int DistinctValues(int arr[], int N)
{
// Stores largest element
// of the array
int max_value = INT_MIN;
// Traverse the array, arr[]
for (int i = 0; i < N; ++i) {
// Update max_value
max_value = max(max_value, arr[i]);
}
// Stores GCD of array
int GCDArr = arr[0];
// Traverse the array, arr[]
for (int i = 1; i < N; ++i) {
// Update GCDArr
GCDArr = gcd(GCDArr, arr[i]);
}
// Stores distinct elements in the array by
// repeatidely inserting absolute difference
// of all possible pairs
int answer = (max_value / GCDArr) + 1;
return answer;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 4, 12, 16, 24 };
int N = sizeof(arr) / sizeof(int);
cout << DistinctValues(arr, N);
return 0;
}
// This code is contributed by hemanth gadarla
Java
// Java program of the above approach
import java.util.*;
class GFG
{
// Function to find the gcd of
// the two numbers
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to find distinct elements in the array
// by repeatidely inserting the absolute difference
// of all possible pairs
static int DistinctValues(int arr[], int N)
{
// Stores largest element
// of the array
int max_value = Integer.MIN_VALUE;
// Traverse the array, arr[]
for (int i = 0; i < N; ++i)
{
// Update max_value
max_value = Math.max(max_value, arr[i]);
}
// Stores GCD of array
int GCDArr = arr[0];
// Traverse the array, arr[]
for (int i = 1; i < N; ++i)
{
// Update GCDArr
GCDArr = gcd(GCDArr, arr[i]);
}
// Stores distinct elements in the array by
// repeatidely inserting absolute difference
// of all possible pairs
int answer = (max_value / GCDArr) + 1;
return answer;
}
// Driver code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 4, 12, 16, 24 };
int N = arr.length;
System.out.println(DistinctValues(arr, N));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program of the above approach import sys # Function to find the gcd of # the two numbers def gcd(a, b): if a == 0: return b return gcd(b % a, a) # Function to find distinct elements in # the array by repeatidely inserting the # absolute difference of all possible pairs def DistinctValues(arr, N): # Stores largest element # of the array max_value = -sys.maxsize - 1 # Update max_value max_value = max(arr) # Stores GCD of array GCDArr = arr[0] # Traverse the array, arr[] for i in range(1, N): # Update GCDArr GCDArr = gcd(GCDArr, arr[i]) # Stores distinct elements in the array by # repeatedely inserting absolute difference # of all possible pairs answer = max_value // GCDArr return answer + 1 # Driver code # Given array arr[] arr = [ 4, 12, 16, 24 ] N = len(arr) print(DistinctValues(arr, N)) # This code is contributed by hemanth gadarla
C#
// C# program of the above approach
using System;
class GFG
{
// Function to find the gcd of
// the two numbers
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to find distinct elements in the array
// by repeatidely inserting the absolute difference
// of all possible pairs
static int DistinctValues(int[] arr, int N)
{
// Stores largest element
// of the array
int max_value = Int32.MinValue;
// Traverse the array, arr[]
for (int i = 0; i < N; ++i)
{
// Update max_value
max_value = Math.Max(max_value, arr[i]);
}
// Stores GCD of array
int GCDArr = arr[0];
// Traverse the array, arr[]
for (int i = 1; i < N; ++i)
{
// Update GCDArr
GCDArr = gcd(GCDArr, arr[i]);
}
// Stores distinct elements in the array by
// repeatidely inserting absolute difference
// of all possible pairs
int answer = (max_value / GCDArr) + 1;
return answer;
}
// Driver code
static void Main()
{
// Given array arr[]
int[] arr = { 4, 12, 16, 24 };
int N = arr.Length;
Console.WriteLine(DistinctValues(arr, N));
}
}
// This code is contributed by susmitakundugoaldanga.
Javascript
<script>
// javascript program of the above approach
// Function to find the gcd of
// the two numbers
function gcd(a , b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to find distinct elements in the array
// by repeatidely inserting the absolute difference
// of all possible pairs
function DistinctValues(arr , N) {
// Stores largest element
// of the array
var max_value = Number.MIN_VALUE;
// Traverse the array, arr
for (i = 0; i < N; ++i) {
// Update max_value
max_value = Math.max(max_value, arr[i]);
}
// Stores GCD of array
var GCDArr = arr[0];
// Traverse the array, arr
for (i = 1; i < N; ++i) {
// Update GCDArr
GCDArr = gcd(GCDArr, arr[i]);
}
// Stores distinct elements in the array by
// repeatidely inserting absolute difference
// of all possible pairs
var answer = (max_value / GCDArr) + 1;
return answer;
}
// Driver code
// Given array arr
var arr = [ 4, 12, 16, 24 ];
var N = arr.length;
document.write(DistinctValues(arr, N));
// This code contributed by gauravrajput1
</script>
7
Complejidad de tiempo: O(N * Min), donde Min es el elemento más pequeño de la array
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ShreyChaurasia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA