Dada una array ordenada arr[] que consta de N elementos distintos, la tarea es encontrar la máxima diferencia común posible de una progresión aritmética tal que la array dada sea una subsecuencia de esa progresión aritmética .
Ejemplos:
Entrada: arr[] = { 2, 4, 6, 8 }
Salida: 2
Explicación:
Dado que arr[] es una subsecuencia de la progresión aritmética { 2, 4, 6, 8, 10, …}, la diferencia común de las la progresión aritmética es 2.Entrada: arr[] = { 2, 5, 11, 23 }
Salida: 3
Explicación:
Dado que arr[] es una subsecuencia de la progresión aritmética { 2, 5, 8, 11, 14, …, 23, …}, la La diferencia común de la progresión aritmética es 2.
Enfoque ingenuo: el enfoque más simple para resolver este problema es iterar sobre el rango [(arr[N – 1] – arr[0]), 1] usando la variable CD (diferencia común) y para cada valor en el rango, verifique si la array dada puede ser un subsiguiente de una progresión aritmética con el primer elemento como arr[0] y la diferencia común como CD . Esto es posible simplemente verificando si la diferencia entre cada par de elementos de array adyacentes es divisible por CD o no. Si se encuentra que es cierto, imprima el valor de CD como la respuesta máxima posible.
Complejidad de tiempo: O(N * (Maxm – Minm)), donde Maxm y Minm son el último y el primer elemento de la array respectivamente.
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
Si arr[i] es el término X y arr [0] es el primer término de una progresión aritmética con diferencia común CD, entonces:
arr[i] = arr[0] + (X – 1) * CD
=> (arr[i] – arr[0]) = (X – 1) * CDPor lo tanto, la máxima diferencia común posible del AP es la GCD de la diferencia absoluta de cada par de elementos de array adyacentes.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos maxCD , para almacenar la diferencia común máxima posible de una progresión aritmética de modo que la array dada sea una subsecuencia de esa progresión aritmética.
- Recorra la array usando la variable i y actualice el valor de maxCD = GCD(maxCD, (arr[i + 1] – arr[i])) .
- Finalmente, imprima el valor de maxCD .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum common
// difference of an AP such that arr[]
// is a subsequence of that AP
int MaxComDiffSubAP(int arr[], int N)
{
// Stores maximum common difference
// of an AP with given conditions
int maxCD = 0;
// Traverse the array
for (int i = 0; i < N - 1; i++) {
// Update maxCD
maxCD = __gcd(maxCD,
arr[i + 1] - arr[i]);
}
return maxCD;
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 7, 9 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << MaxComDiffSubAP(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
class GFG
{
// Recursive function to return gcd of a and b
static int gcd(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 gcd(a - b, b);
return gcd(a, b - a);
}
// Function to find the maximum common
// difference of an AP such that arr[]
// is a subsequence of that AP
static int MaxComDiffSubAP(int arr[], int N)
{
// Stores maximum common difference
// of an AP with given conditions
int maxCD = 0;
// Traverse the array
for (int i = 0; i < N - 1; i++)
{
// Update maxCD
maxCD = gcd(maxCD,
arr[i + 1] - arr[i]);
}
return maxCD;
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 1, 3, 7, 9 };
int N = arr.length;
System.out.print(MaxComDiffSubAP(arr, N));
}
}
// This code is contributed by AnkThon
Python3
# Python3 program to implement # the above approach from math import gcd # Function to find the maximum common # difference of an AP such that arr[] # is a subsequence of that AP def MaxComDiffSubAP(arr, N): # Stores maximum common difference # of an AP with given conditions maxCD = 0 # Traverse the array for i in range(N - 1): # Update maxCD maxCD = gcd(maxCD, arr[i + 1] - arr[i]) return maxCD # Driver Code if __name__ == '__main__': arr = [ 1, 3, 7, 9 ] N = len(arr) print(MaxComDiffSubAP(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Recursive function to return
// gcd of a and b
static int gcd(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 gcd(a - b, b);
return gcd(a, b - a);
}
// Function to find the maximum common
// difference of an AP such that arr[]
// is a subsequence of that AP
static int MaxComDiffSubAP(int[] arr, int N)
{
// Stores maximum common difference
// of an AP with given conditions
int maxCD = 0;
// Traverse the array
for(int i = 0; i < N - 1; i++)
{
// Update maxCD
maxCD = gcd(maxCD,
arr[i + 1] - arr[i]);
}
return maxCD;
}
// Driver Code
public static void Main ()
{
int[] arr = { 1, 3, 7, 9 };
int N = arr.Length;
Console.WriteLine(MaxComDiffSubAP(arr, N));
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// Javascript program for the above approach
// Recursive function to return gcd of a and b
function gcd(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 gcd(a - b, b);
return gcd(a, b - a);
}
// Function to find the maximum common
// difference of an AP such that arr[]
// is a subsequence of that AP
function MaxComDiffSubAP(arr, N)
{
// Stores maximum common difference
// of an AP with given conditions
let maxCD = 0;
// Traverse the array
for(let i = 0; i < N - 1; i++)
{
// Update maxCD
maxCD = gcd(maxCD,
arr[i + 1] - arr[i]);
}
return maxCD;
}
// Driver Code
let arr = [ 1, 3, 7, 9 ];
let N = arr.length;
document.write(MaxComDiffSubAP(arr, N));
// This code is contributed by splevel62
</script>
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)