Dada una array arr[] que consta de N enteros positivos y un entero positivo K , la tarea es maximizar el GCD de la array arr[] aumentando o disminuyendo cualquier elemento de la array en K .
Ejemplos:
Entrada: arr[] = {3, 9, 15, 24}, K = 1
Salida: 4
Explicación:
Realice las siguientes operaciones en la array arr[]:
Incremente arr[0] en 1. Por lo tanto, arr[] se modifica a {4, 9, 15, 24}.
Decrementa arr[1] en 1. Por lo tanto, arr[] se modifica a {4, 8, 15, 24}.
Incrementa arr[2] en 1. Por lo tanto, arr[] se modifica a {4, 8, 16, 24}.
Por lo tanto, GCD de la array modificada es 4.Entrada: arr[] = {5, 9, 2}, K = 1
Salida: 3
Enfoque ingenuo: el enfoque más simple para resolver este problema es considerar las tres opciones para cada elemento de array arr[i] , es decir, aumentar arr[i] en K , disminuir arr[i] en K o ni incrementar ni decrementar arr[i ] . Genere las arrays formadas en los 3 casos usando recursividad e imprima el máximo de GCD de todas las arrays obtenidas.
Complejidad de Tiempo: O(3 N )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante la programación dinámica . Siga los pasos a continuación para resolver el problema dado:
- Inicialice una array auxiliar, digamos dp[][3] , donde dp[i][0] , dp[i][1] y dp[i][2] denotan el GCD máximo posible hasta el i -ésimo índice sin cambiar los i -ésimos elementos , incrementando o decrementando el i -ésimo elemento en K respectivamente.
- Rellene la primera fila de dp[][3] actualizando dp[0][0] , dp[0][1] y dp[0][2] con arr[0] , arr[0] + K y arr [0] – K respectivamente.
- Iterar sobre el rango [1, N – 1] y realizar los siguientes pasos:
- Para dp[i][0] , encuentre el MCD máximo de A[i] con 3 estados previos, es decir, dp[i – 1][0], dp[i – 1][1] y dp[i – 1 ][2] una vez y almacene el resultado máximo en dp[i][0] .
- De manera similar, almacene los resultados en dp[i][1] y dp[i][2] tomando (arr[i] + K) y (arr[i] – K) respectivamente.
- Después de completar los pasos anteriores, imprima el valor máximo en la fila dp[N – 1] como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to return the maximum GCD // by taking each operation int findGCD(int x, int y, int z, int res) { // Store the maximum GCD obtained // by either incrementing, decrementing // or not changing A[i] int ans = __gcd(x, res); ans = max(ans, __gcd(y, res)); ans = max(ans, __gcd(z, res)); // Return the maximum GCD return ans; } // Function to find the maximum GCD of // the array arrA[] by either increasing // or decreasing the array elements by K int maximumGCD(int A[], int N, int K) { // Initialize a dp table of size N*3 int dp[N][3]; memset(dp, 0, sizeof(dp)); // Base Cases: // If only one element is present dp[0][0] = A[0]; dp[0][1] = A[0] + K; dp[0][2] = A[0] - K; // Traverse the array A[] over indices [1, N - 1] for (int i = 1; i < N; i++) { // Store the previous state results int x = dp[i - 1][0]; int y = dp[i - 1][1]; int z = dp[i - 1][2]; // Store maximum GCD result // for each current state dp[i][0] = findGCD(x, y, z, A[i]); dp[i][1] = findGCD(x, y, z, A[i] + K); dp[i][2] = findGCD(x, y, z, A[i] - K); } // Store the required result int mx = max( { 3, dp[N - 1][0], dp[N - 1][1], dp[N - 1][2] }); // Return the result return mx; } // Driver Code int main() { int arr[] = { 3, 9, 15, 24 }; int K = 1; int N = sizeof(arr) / sizeof(arr[0]); cout << maximumGCD(arr, N, K); return 0; }
Java
// Java program for the above approach import java.io.*; import java.util.*; 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 return the maximum GCD // by taking each operation static int findGCD(int x, int y, int z, int res) { // Store the maximum GCD obtained // by either incrementing, decrementing // or not changing A[i] int ans = gcd(x, res); ans = Math.max(ans, gcd(y, res)); ans = Math.max(ans, gcd(z, res)); // Return the maximum GCD return ans; } // Function to find the maximum GCD of // the array arrA[] by either increasing // or decreasing the array elements by K static int maximumGCD(int A[], int N, int K) { // Initialize a dp table of size N*3 int dp[][] = new int[N][3]; for (int i = 0; i < N; i++) { for (int j = 1; j < 3; j++) { dp[i][j] = 0; } } // Base Cases: // If only one element is present dp[0][0] = A[0]; dp[0][1] = A[0] + K; dp[0][2] = A[0] - K; // Traverse the array A[] over indices [1, N - 1] for (int i = 1; i < N; i++) { // Store the previous state results int x = dp[i - 1][0]; int y = dp[i - 1][1]; int z = dp[i - 1][2]; // Store maximum GCD result // for each current state dp[i][0] = findGCD(x, y, z, A[i]); dp[i][1] = findGCD(x, y, z, A[i] + K); dp[i][2] = findGCD(x, y, z, A[i] - K); } // Store the required result int mx = Math.max(3, Math.max(dp[N - 1][0], Math.max(dp[N - 1][1], dp[N - 1][2]))); // Return the result return mx; } // Driver code public static void main(String[] args) { int arr[] = { 3, 9, 15, 24 }; int K = 1; int N = arr.length; System.out.print( maximumGCD(arr, N, K)); } } // This code is contributed by sanjoy_62.
Python3
# Python3 program for the above approach import math # Function to return the maximum GCD # by taking each operation def findGCD(x, y, z, res): # Store the maximum GCD obtained # by either incrementing, decrementing # or not changing A[i] ans = math.gcd(x, res) ans = max(ans, math.gcd(y, res)) ans = max(ans, math.gcd(z, res)) # Return the maximum GCD return ans # Function to find the maximum GCD of # the array arrA[] by either increasing # or decreasing the array elements by K def maximumGCD(A, N, K): # Initialize a dp table of size N*3 dp = [[0 for x in range(3)] for y in range(N)] # Base Cases: # If only one element is present dp[0][0] = A[0] dp[0][1] = A[0] + K dp[0][2] = A[0] - K # Traverse the array A[] over # indices [1, N - 1] for i in range(1, N): # Store the previous state results x = dp[i - 1][0] y = dp[i - 1][1] z = dp[i - 1][2] # Store maximum GCD result # for each current state dp[i][0] = findGCD(x, y, z, A[i]) dp[i][1] = findGCD(x, y, z, A[i] + K) dp[i][2] = findGCD(x, y, z, A[i] - K) # Store the required result mx = max([3, dp[N - 1][0], dp[N - 1][1], dp[N - 1][2]]) # Return the result return mx # Driver Code if __name__ == "__main__": arr = [ 3, 9, 15, 24 ] K = 1 N = len(arr) print(maximumGCD(arr, N, K)) # This code is contributed by chitranayal
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 return the maximum GCD // by taking each operation static int findGCD(int x, int y, int z, int res) { // Store the maximum GCD obtained // by either incrementing, decrementing // or not changing A[i] int ans = gcd(x, res); ans = Math.Max(ans, gcd(y, res)); ans = Math.Max(ans, gcd(z, res)); // Return the maximum GCD return ans; } // Function to find the maximum GCD of // the array arrA[] by either increasing // or decreasing the array elements by K static int maximumGCD(int[] A, int N, int K) { // Initialize a dp table of size N*3 int[,] dp = new int[N, 3]; for (int i = 0; i < N; i++) { for (int j = 1; j < 3; j++) { dp[i, j] = 0; } } // Base Cases: // If only one element is present dp[0, 0] = A[0]; dp[0, 1] = A[0] + K; dp[0, 2] = A[0] - K; // Traverse the array A[] over indices [1, N - 1] for (int i = 1; i < N; i++) { // Store the previous state results int x = dp[i - 1, 0]; int y = dp[i - 1, 1]; int z = dp[i - 1, 2]; // Store maximum GCD result // for each current state dp[i, 0] = findGCD(x, y, z, A[i]); dp[i, 1] = findGCD(x, y, z, A[i] + K); dp[i, 2] = findGCD(x, y, z, A[i] - K); } // Store the required result int mx = Math.Max(3, Math.Max(dp[N - 1, 0], Math.Max(dp[N - 1, 1], dp[N - 1, 2]))); // Return the result return mx; } // Driver code public static void Main() { int[] arr = { 3, 9, 15, 24 }; int K = 1; int N = arr.Length; Console.Write( maximumGCD(arr, N, K)); } } // This code is contributed by susmitakundugoaldanga.
Javascript
<script> //Javascript program for the above approach 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 findGCD(x, y, z, res) { // Store the maximum GCD obtained // by either incrementing, decrementing // or not changing A[i] var ans = gcd(x, res); ans = Math.max(ans, gcd(y, res)); ans = Math.max(ans, gcd(z, res)); // Return the maximum GCD return ans; } // Function to find the maximum GCD of // the array arrA[] by either increasing // or decreasing the array elements by K function maximumGCD( A, N, K) { // Initialize a dp table of size N*3 var dp = new Array(N).fill(0).map(() => new Array(3).fill(0)); // Base Cases: // If only one element is present dp[0][0] = A[0]; dp[0][1] = A[0] + K; dp[0][2] = A[0] - K; // Traverse the array A[] over indices [1, N - 1] for (var i = 1; i < N; i++) { // Store the previous state results var x = dp[i - 1][0]; var y = dp[i - 1][1]; var z = dp[i - 1][2]; // Store maximum GCD result // for each current state dp[i][0] = findGCD(x, y, z, A[i]); dp[i][1] = findGCD(x, y, z, A[i] + K); dp[i][2] = findGCD(x, y, z, A[i] - K); } // Store the required result var mx = Math.max(3, Math.max(dp[N - 1][0], Math.max(dp[N - 1][1], dp[N - 1][2]))); // Return the result return mx; } var arr = [ 3, 9, 15, 24 ]; var K = 1; var N = arr.length; document.write( maximumGCD(arr, N, K)); //This code is contributed by SoumikMondal </script>
4
Complejidad de tiempo: O(N*log(M)), donde M es el elemento más pequeño de la array arr[]
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA