Máximo GCD posible después de reemplazar como máximo un elemento en la array dada

Posted on by Rudeus Greyrat

Dada una array arr[] de tamaño N > 1 . La tarea es encontrar el GCD máximo posible de la array reemplazando como máximo un elemento.
Ejemplos: 
 

Entrada: arr[] = {6, 7, 8} 
Salida: 2 
Reemplace 7 con 2 y mcd(6, 2, 8) = 2, 
que es el máximo posible.
Entrada: arr[] = {12, 18, 30} 
Salida: 6 
 

Acercarse: 
 

  • La idea es encontrar el valor GCD de todas las subsecuencias de longitud (N – 1) y eliminar el elemento que debe reemplazarse en la subsecuencia, ya que puede reemplazarse con cualquier otro elemento que ya esté en la subsecuencia. El GCD máximo encontrado sería la respuesta.
  • Para encontrar el GCD de las subsecuencias de manera óptima, mantenga una array prefixGCD[] y suffixGCD[] utilizando programación dinámica de un solo estado .
  • El valor máximo de GCD (prefijo GCD [i – 1], sufijo GCD [i + 1]) es la respuesta requerida. También tenga en cuenta que el sufijo GCD [1] y el prefijo GCD [N – 2] también deben compararse en caso de que se deba reemplazar el primer o el último elemento.

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum
// possible gcd after replacing
// a single element
int MaxGCD(int a[], int n)
{
 
    // Prefix and Suffix arrays
    int Prefix[n + 2];
    int Suffix[n + 2];
 
    // Single state dynamic programming relation
    // for storing gcd of first i elements
    // from the left in Prefix[i]
    Prefix[1] = a[0];
    for (int i = 2; i <= n; i += 1) {
        Prefix[i] = __gcd(Prefix[i - 1], a[i - 1]);
    }
 
    // Initializing Suffix array
    Suffix[n] = a[n - 1];
 
    // Single state dynamic programming relation
    // for storing gcd of all the elements having
    // index greater than or equal to i in Suffix[i]
    for (int i = n - 1; i >= 1; i -= 1) {
        Suffix[i] = __gcd(Suffix[i + 1], a[i - 1]);
    }
 
    // If first or last element of
    // the array has to be replaced
    int ans = max(Suffix[2], Prefix[n - 1]);
 
    // If any other element is replaced
    for (int i = 2; i < n; i += 1) {
        ans = max(ans, __gcd(Prefix[i - 1], Suffix[i + 1]));
    }
 
    // Return the maximized gcd
    return ans;
}
 
// Driver code
int main()
{
    int a[] = { 6, 7, 8 };
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << MaxGCD(a, n);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
 
// Function to return the maximum
// possible gcd after replacing
// a single element
static int MaxGCD(int a[], int n)
{
 
    // Prefix and Suffix arrays
    int []Prefix = new int[n + 2];
    int []Suffix = new int[n + 2];
 
    // Single state dynamic programming relation
    // for storing gcd of first i elements
    // from the left in Prefix[i]
    Prefix[1] = a[0];
    for (int i = 2; i <= n; i += 1)
    {
        Prefix[i] = __gcd(Prefix[i - 1],
                               a[i - 1]);
    }
 
    // Initializing Suffix array
    Suffix[n] = a[n - 1];
 
    // Single state dynamic programming relation
    // for storing gcd of all the elements having
    // index greater than or equal to i in Suffix[i]
    for (int i = n - 1; i >= 1; i -= 1)
    {
        Suffix[i] = __gcd(Suffix[i + 1],
                               a[i - 1]);
    }
 
    // If first or last element of
    // the array has to be replaced
    int ans = Math.max(Suffix[2], Prefix[n - 1]);
 
    // If any other element is replaced
    for (int i = 2; i < n; i += 1)
    {
        ans = Math.max(ans, __gcd(Prefix[i - 1],
                                  Suffix[i + 1]));
    }
 
    // Return the maximized gcd
    return ans;
}
 
static int __gcd(int a, int b)
{
    return b == 0 ? a : __gcd(b, a % b);    
}
 
// Driver code
public static void main(String[] args)
{
    int a[] = { 6, 7, 8 };
    int n = a.length;
 
    System.out.println(MaxGCD(a, n));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of the approach
from math import gcd as __gcd
 
# Function to return the maximum
# possible gcd after replacing
# a single element
def MaxGCD(a, n) :
 
    # Prefix and Suffix arrays
    Prefix = [0] * (n + 2);
    Suffix = [0] * (n + 2);
 
    # Single state dynamic programming relation
    # for storing gcd of first i elements
    # from the left in Prefix[i]
    Prefix[1] = a[0];
     
    for i in range(2, n + 1) :
        Prefix[i] = __gcd(Prefix[i - 1], a[i - 1]);
 
    # Initializing Suffix array
    Suffix[n] = a[n - 1];
 
    # Single state dynamic programming relation
    # for storing gcd of all the elements having
    # index greater than or equal to i in Suffix[i]
    for i in range(n - 1, 0, -1) :
        Suffix[i] = __gcd(Suffix[i + 1], a[i - 1]);
 
    # If first or last element of
    # the array has to be replaced
    ans = max(Suffix[2], Prefix[n - 1]);
 
    # If any other element is replaced
    for i in range(2, n) :
        ans = max(ans, __gcd(Prefix[i - 1],
                             Suffix[i + 1]));
 
    # Return the maximized gcd
    return ans;
 
# Driver code
if __name__ == "__main__" :
 
    a = [ 6, 7, 8 ];
    n = len(a);
 
    print(MaxGCD(a, n));
 
# This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
     
class GFG
{
 
// Function to return the maximum
// possible gcd after replacing
// a single element
static int MaxGCD(int []a, int n)
{
 
    // Prefix and Suffix arrays
    int []Prefix = new int[n + 2];
    int []Suffix = new int[n + 2];
 
    // Single state dynamic programming relation
    // for storing gcd of first i elements
    // from the left in Prefix[i]
    Prefix[1] = a[0];
    for (int i = 2; i <= n; i += 1)
    {
        Prefix[i] = __gcd(Prefix[i - 1],
                            a[i - 1]);
    }
 
    // Initializing Suffix array
    Suffix[n] = a[n - 1];
 
    // Single state dynamic programming relation
    // for storing gcd of all the elements having
    // index greater than or equal to i in Suffix[i]
    for (int i = n - 1; i >= 1; i -= 1)
    {
        Suffix[i] = __gcd(Suffix[i + 1],
                            a[i - 1]);
    }
 
    // If first or last element of
    // the array has to be replaced
    int ans = Math.Max(Suffix[2], Prefix[n - 1]);
 
    // If any other element is replaced
    for (int i = 2; i < n; i += 1)
    {
        ans = Math.Max(ans, __gcd(Prefix[i - 1],
                                Suffix[i + 1]));
    }
 
    // Return the maximized gcd
    return ans;
}
 
static int __gcd(int a, int b)
{
    return b == 0 ? a : __gcd(b, a % b);    
}
 
// Driver code
public static void Main(String[] args)
{
    int []a = { 6, 7, 8 };
    int n = a.Length;
 
    Console.WriteLine(MaxGCD(a, n));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript implementation of the approach
 
function gcd(a, b) {
  if (b==0) {
    return a;
  }
 
  return gcd(b, a % b);
}
// Function to return the maximum
// possible gcd after replacing
// a single element
function MaxGCD(a, n)
{
 
    // Prefix and Suffix arrays
    var Prefix = Array(n + 2).fill(0);
    var Suffix = Array(n + 2).fill(0);
 
    var i;
    // Single state dynamic programming relation
    // for storing gcd of first i elements
    // from the left in Prefix[i]
    Prefix[1] = a[0];
    for (i = 2; i <= n; i++) {
        Prefix[i] = gcd(Prefix[i - 1], a[i - 1]);
    }
 
    // Initializing Suffix array
    Suffix[n] = a[n - 1];
 
    // Single state dynamic programming relation
    // for storing gcd of all the elements having
    // index greater than or equal to i in Suffix[i]
    for (i = n - 1; i >= 1; i--) {
        Suffix[i] = gcd(Suffix[i + 1], a[i - 1]);
    }
 
    // If first or last element of
    // the array has to be replaced
    var ans = Math.max(Suffix[2], Prefix[n - 1]);
 
    // If any other element is replaced
    for (i = 2; i < n; i++) {
        ans = Math.max(ans, gcd(Prefix[i - 1],
        Suffix[i + 1]));
    }
 
    // Return the maximized gcd
    return ans;
}
 
// Driver code
    var a = [6, 7, 8];
    n = a.length;
 
    document.write(MaxGCD(a, n));
 
</script>
Producción: 

2

 

Complejidad de tiempo: O(n * max(a, b))

Espacio Auxiliar: O(n)

Publicación traducida automáticamente

Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *