Рубрики

Максимально возможный GCD после замены не более одного элемента в данном массиве

Дан массив arr [] размером N> 1 . Задача состоит в том, чтобы найти максимально возможный GCD массива, заменив не более одного элемента.

Примеры:

Input: arr[] = {6, 7, 8}
Output: 2
Replace 7 with 2 and gcd(6, 2, 8) = 2
which is maximum possible.

Input: arr[] = {12, 18, 30}
Output: 6

Подходить:

  • Идея состоит в том, чтобы найти значение GCD всех подпоследовательностей длины (N — 1) и удалить элемент, который должен быть заменен в подпоследовательности, поскольку его можно заменить любым другим элементом, уже находящимся в подпоследовательности. Максимальный найденный GCD был бы ответом.
  • Чтобы найти GCD подпоследовательностей оптимально, сохраните префикс GCD [] и суффикс GCD [], используя динамическое программирование в одном состоянии.
  • Максимальное значение GCD (префикс GCD [i — 1], суффикс GCD [i + 1]) является обязательным ответом. Также обратите внимание, что суффиксы GCD [1] и prefixGCD [N — 2] также необходимо сравнивать в случае замены первого или последнего элемента.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата максимума
// возможно gcd после замены
// один элемент

int MaxGCD(int a[], int n)

{

  

    // Префиксный и суффиксный массивы

    int Prefix[n + 2];

    int Suffix[n + 2];

  

    // динамическое программирование одного состояния

    // для хранения gcd первых элементов i

    // слева в префиксе [i]

    Prefix[1] = a[0];

    for (int i = 2; i <= n; i += 1) {

        Prefix[i] = __gcd(Prefix[i - 1], a[i - 1]);

    }

  

    // Инициализация суффиксного массива

    Suffix[n] = a[n - 1];

  

    // динамическое программирование одного состояния

    // для хранения gcd всех элементов, имеющих

    // индекс больше или равен i в суффиксе [i]

    for (int i = n - 1; i >= 1; i -= 1) {

        Suffix[i] = __gcd(Suffix[i + 1], a[i - 1]);

    }

  

    // Если первый или последний элемент

    // массив должен быть заменен

    int ans = max(Suffix[2], Prefix[n - 1]);

  

    // Если любой другой элемент заменен

    for (int i = 2; i < n; i += 1) {

        ans = max(ans, __gcd(Prefix[i - 1], Suffix[i + 1]));

    }

  

    // Возвращаем развернутый gcd

    return ans;

}

  
// Код драйвера

int main()

{

    int a[] = { 6, 7, 8 };

    int n = sizeof(a) / sizeof(a[0]);

  

    cout << MaxGCD(a, n);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG 

{

  
// Функция для возврата максимума
// возможно gcd после замены
// один элемент

static int MaxGCD(int a[], int n)

{

  

    // Префиксный и суффиксный массивы

    int []Prefix = new int[n + 2];

    int []Suffix = new int[n + 2];

  

    // динамическое программирование одного состояния

    // для хранения gcd первых элементов i

    // слева в префиксе [i]

    Prefix[1] = a[0];

    for (int i = 2; i <= n; i += 1

    {

        Prefix[i] = __gcd(Prefix[i - 1], 

                               a[i - 1]);

    }

  

    // Инициализация суффиксного массива

    Suffix[n] = a[n - 1];

  

    // динамическое программирование одного состояния

    // для хранения gcd всех элементов, имеющих

    // индекс больше или равен i в суффиксе [i]

    for (int i = n - 1; i >= 1; i -= 1

    {

        Suffix[i] = __gcd(Suffix[i + 1], 

                               a[i - 1]);

    }

  

    // Если первый или последний элемент

    // массив должен быть заменен

    int ans = Math.max(Suffix[2], Prefix[n - 1]);

  

    // Если любой другой элемент заменен

    for (int i = 2; i < n; i += 1)

    {

        ans = Math.max(ans, __gcd(Prefix[i - 1], 

                                  Suffix[i + 1]));

    }

  

    // Возвращаем развернутый gcd

    return ans;

}

  

static int __gcd(int a, int b) 

    return b == 0 ? a : __gcd(b, a % b);     

}

  
// Код драйвера

public static void main(String[] args) 

{

    int a[] = { 6, 7, 8 };

    int n = a.length;

  

    System.out.println(MaxGCD(a, n));

}
}

  
// Этот код предоставлен PrinciRaj1992

python3

# Python3 реализация подхода

from math import gcd as __gcd

  
# Функция для возврата максимума
# возможно жкд после замены
# один элемент

def MaxGCD(a, n) :

  

    # Префикс и суффикс массивов

    Prefix = [0] * (n + 2); 

    Suffix = [0] * (n + 2); 

  

    # Одно состояние динамического программирования отношения

    # для хранения gcd первых элементов i

    # слева в префиксе [i]

    Prefix[1] = a[0]; 

      

    for i in range(2, n + 1) :

        Prefix[i] = __gcd(Prefix[i - 1], a[i - 1]); 

  

    # Инициализация суффиксного массива

    Suffix[n] = a[n - 1]; 

  

    # Одно состояние динамического программирования отношения

    # для хранения gcd всех элементов, имеющих

    # индекс больше или равен i в суффиксе [i]

    for i in range(n - 1, 0, -1) :

        Suffix[i] = __gcd(Suffix[i + 1], a[i - 1]); 

  

    # Если первый или последний элемент

    # массив должен быть заменен

    ans = max(Suffix[2], Prefix[n - 1]); 

  

    # Если любой другой элемент заменен

    for i in range(2, n) :

        ans = max(ans, __gcd(Prefix[i - 1], 

                             Suffix[i + 1])); 

  

    # Вернуть развернутый gcd

    return ans; 

  
# Код драйвера

if __name__ == "__main__" :

  

    a = [ 6, 7, 8 ]; 

    n = len(a); 

  

    print(MaxGCD(a, n)); 

  
# Этот код предоставлен AnkitRai01

C #

// C # реализация подхода

using System;

      

class GFG 

{

  
// Функция для возврата максимума
// возможно gcd после замены
// один элемент

static int MaxGCD(int []a, int n)

{

  

    // Префиксный и суффиксный массивы

    int []Prefix = new int[n + 2];

    int []Suffix = new int[n + 2];

  

    // динамическое программирование одного состояния

    // для хранения gcd первых элементов i

    // слева в префиксе [i]

    Prefix[1] = a[0];

    for (int i = 2; i <= n; i += 1) 

    {

        Prefix[i] = __gcd(Prefix[i - 1], 

                            a[i - 1]);

    }

  

    // Инициализация суффиксного массива

    Suffix[n] = a[n - 1];

  

    // динамическое программирование одного состояния

    // для хранения gcd всех элементов, имеющих

    // индекс больше или равен i в суффиксе [i]

    for (int i = n - 1; i >= 1; i -= 1) 

    {

        Suffix[i] = __gcd(Suffix[i + 1], 

                            a[i - 1]);

    }

  

    // Если первый или последний элемент

    // массив должен быть заменен

    int ans = Math.Max(Suffix[2], Prefix[n - 1]);

  

    // Если любой другой элемент заменен

    for (int i = 2; i < n; i += 1)

    {

        ans = Math.Max(ans, __gcd(Prefix[i - 1], 

                                Suffix[i + 1]));

    }

  

    // Возвращаем развернутый gcd

    return ans;

}

  

static int __gcd(int a, int b) 

    return b == 0 ? a : __gcd(b, a % b);     

}

  
// Код драйвера

public static void Main(String[] args) 

{

    int []a = { 6, 7, 8 };

    int n = a.Length;

  

    Console.WriteLine(MaxGCD(a, n));

}
}

  
// Этот код предоставлен 29AjayKumar

Выход:

2

Рекомендуемые посты:

Максимально возможный GCD после замены не более одного элемента в данном массиве

0.00 (0%) 0 votes