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>
Producción:
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