Dada una array de enteros Arr[] . Los elementos de la array se ordenan en orden creciente. La tarea es encontrar el número mínimo de elementos que se insertarán en la array para que las diferencias entre dos elementos consecutivos cualesquiera sean las mismas.
Ejemplos:
Entrada: Arr[] = {1, 4, 13, 19, 25}
Salida: 4
Explicación:
Una solución posible es: Arr[] = { 1, 4, 7, 10, 13, 16, 19, 22, 25 } . Aquí todos los elementos consecutivos tienen una diferencia de 3, para esto se insertan 4 elementos.Entrada: Arr[] = {1, 5, 8, 10, 12, 16};
Salida: 10
Explicación:
se deben insertar 10 elementos para que la diferencia sea igual.
Enfoque: La idea es calcular las diferencias entre todos los elementos consecutivos. Hay N elementos en la array, por lo que habrá N – 1 de esa diferencia.
- Encuentre el MCD (máximo común divisor) de todas esas diferencias. Este GCD será la diferencia entre dos elementos consecutivos de la array después de la inserción de nuevos elementos.
- Supongamos que la diferencia entre el primer y el segundo elemento es diff . Inicialice la respuesta por 0 y agregue ((diff / GCD) – 1) a la respuesta porque hay (diff / GCD – 1) elementos que se necesitan para hacer que la diferencia sea igual a GCD .
- Realice lo mismo para todos los elementos consecutivos de la array dada y agregue a la respuesta para encontrar la cantidad mínima de elementos que se insertarán para hacer diferencias iguales entre dos elementos consecutivos cualesquiera de la array.
A continuación se muestra la implementación del enfoque:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to find gcd of two numbers
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to calculate minimum
// numbers to be inserted to make
// equal differences between
// two consecutive elements
int minimum_elements(int n, int arr[])
{
// Check if there is only one
// element in the array
// then answer will be 0
if (n < 3)
return 0;
int g, ans = 0, diff, cnt;
// Calculate difference
// between first and second
// element of array
diff = arr[1] - arr[0];
// If there is only two elements
// in the array then gcd of
// differences of consecutive
// elements of array will be
// equal to difference of first
// and second element of the array
g = diff;
// Loop to calculate the gcd
// of the differences between
// consecutive elements of the array
for (int i = 2; i < n; i++) {
diff = arr[i] - arr[i - 1];
g = gcd(g, diff);
}
// Loop to calculate the
// elements to be inserted
for (int i = 1; i < n; i++) {
diff = arr[i] - arr[i - 1];
cnt = diff / g;
ans += (cnt - 1);
}
// Return the answer
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 5, 8, 10, 12, 16 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << minimum_elements(n, arr);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find gcd of two numbers
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to calculate minimum
// numbers to be inserted to make
// equal differences between
// two consecutive elements
static int minimum_elements(int n, int arr[])
{
// Check if there is only one
// element in the array
// then answer will be 0
if (n < 3)
return 0;
int g, ans = 0, diff, cnt;
// Calculate difference
// between first and second
// element of array
diff = arr[1] - arr[0];
// If there is only two elements
// in the array then gcd of
// differences of consecutive
// elements of array will be
// equal to difference of first
// and second element of the array
g = diff;
// Loop to calculate the gcd
// of the differences between
// consecutive elements of the array
for(int i = 2; i < n; i++)
{
diff = arr[i] - arr[i - 1];
g = gcd(g, diff);
}
// Loop to calculate the
// elements to be inserted
for(int i = 1; i < n; i++)
{
diff = arr[i] - arr[i - 1];
cnt = diff / g;
ans += (cnt - 1);
}
// Return the answer
return ans;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 1, 5, 8, 10, 12, 16 };
int n = arr.length;
System.out.println(minimum_elements(n, arr));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach # Function to find gcd of two numbers def gcd(a, b): if (b == 0): return a return gcd(b, a % b) # Function to calculate minimum # numbers to be inserted to make # equal differences between # two consecutive elements def minimum_elements(n, arr): # Check if there is only one # element in the array # then answer will be 0 if (n < 3): return 0 ans = 0 # Calculate difference # between first and second # element of array diff = arr[1] - arr[0] # If there is only two elements # in the array then gcd of # differences of consecutive # elements of array will be # equal to difference of first # and second element of the array g = diff # Loop to calculate the gcd # of the differences between # consecutive elements of the array for i in range(2, n): diff = arr[i] - arr[i - 1] g = gcd(g, diff) # Loop to calculate the # elements to be inserted for i in range(1, n): diff = arr[i] - arr[i - 1] cnt = diff // g ans += (cnt - 1) # Return the answer return ans # Driver code arr = [ 1, 5, 8, 10, 12, 16 ] n = len(arr) print(minimum_elements(n, arr)) # This code is contributed by sanjoy_62
C#
// C# program for the above approach
using System;
class GFG{
// Function to find gcd of two numbers
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to calculate minimum
// numbers to be inserted to make
// equal differences between
// two consecutive elements
static int minimum_elements(int n, int[] arr)
{
// Check if there is only one
// element in the array
// then answer will be 0
if (n < 3)
return 0;
int g, ans = 0, diff, cnt;
// Calculate difference
// between first and second
// element of array
diff = arr[1] - arr[0];
// If there is only two elements
// in the array then gcd of
// differences of consecutive
// elements of array will be
// equal to difference of first
// and second element of the array
g = diff;
// Loop to calculate the gcd
// of the differences between
// consecutive elements of the array
for(int i = 2; i < n; i++)
{
diff = arr[i] - arr[i - 1];
g = gcd(g, diff);
}
// Loop to calculate the
// elements to be inserted
for(int i = 1; i < n; i++)
{
diff = arr[i] - arr[i - 1];
cnt = diff / g;
ans += (cnt - 1);
}
// Return the answer
return ans;
}
// Driver code
public static void Main ()
{
int[] arr = { 1, 5, 8, 10, 12, 16 };
int n = arr.Length;
Console.WriteLine(minimum_elements(n, arr));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for the above approach
// Function to find gcd of two numbers
function gcd(a, b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to calculate minimum
// numbers to be inserted to make
// equal differences between
// two consecutive elements
function minimum_elements(n, arr)
{
// Check if there is only one
// element in the array
// then answer will be 0
if (n < 3)
return 0;
let g, ans = 0, diff, cnt;
// Calculate difference
// between first and second
// element of array
diff = arr[1] - arr[0];
// If there is only two elements
// in the array then gcd of
// differences of consecutive
// elements of array will be
// equal to difference of first
// and second element of the array
g = diff;
// Loop to calculate the gcd
// of the differences between
// consecutive elements of the array
for (let i = 2; i < n; i++) {
diff = arr[i] - arr[i - 1];
g = gcd(g, diff);
}
// Loop to calculate the
// elements to be inserted
for (let i = 1; i < n; i++) {
diff = arr[i] - arr[i - 1];
cnt = parseInt(diff / g);
ans += (cnt - 1);
}
// Return the answer
return ans;
}
// Driver code
let arr = [ 1, 5, 8, 10, 12, 16 ];
let n = arr.length;
document.write(minimum_elements(n, arr));
</script>
Producción:
10
Complejidad de Tiempo: O(N * log N)
Espacio Auxiliar: O(1), ya que no se ha tomado espacio extra.
Publicación traducida automáticamente
Artículo escrito por Vivek.Pandit y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA