Given an array arr[] of size N > 1. The task is to find the maximum possible GCD of the array by replacing at most one element.
Examples:
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
Approach:
- Idea is to find the GCD value of all the sub-sequences of length (N – 1) and removing the element which has to be replaced in the sub-sequence as it can be replaced with any other element already in the subsequence. The maximum GCD found would be the answer.
- To find the GCD of the sub-sequences optimally, maintain a prefixGCD[] and a suffixGCD[] array using single state dynamic programming.
- The maximum value of GCD(prefixGCD[i – 1], suffixGCD[i + 1]) is the required answer. Also note that suffixGCD[1] and prefixGCD[N – 2] also need to be compared in case the first or the last element has to be replaced.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the maximum possible gcd after// replacing a single elementint 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 codeint main(){ int a[] = { 6, 7, 8 }; int n = sizeof(a) / sizeof(a[0]); printf("%d", MaxGCD(a, n)); return 0;} |
C
// C implementation of the approach#include <stdio.h>// Find maximum between two numbers.int max(int num1, int num2){ return (num1 > num2) ? num1 : num2;}// Find minimum between two numbers.int min(int num1, int num2){ return (num1 > num2) ? num2 : num1;}// Function to return gcd of a and bint gcd(int a, int b){ int result = min(a, b); // Finding minimum of a nd b while (result > 0) { if (a % result == 0 && b % result == 0) { break; } result--; } return result; // return gcd of a nd b}// Function to return the maximum possible gcd after// replacing a single elementint 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 codeint main(){ int a[] = { 6, 7, 8 }; int n = sizeof(a) / sizeof(a[0]); printf("%d", MaxGCD(a, n)); return 0;}// This code is contributed by Sania Kumari Gupta |
Java
// Java implementation of the approachclass GFG {// Function to return the maximum// possible gcd after replacing// a single elementstatic 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 codepublic 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 approachusing System; class GFG {// Function to return the maximum// possible gcd after replacing// a single elementstatic 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 codepublic 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 approachfunction gcd(a, b) { if (b==0) { return a; } return gcd(b, a % b);}// Function to return the maximum// possible gcd after replacing// a single elementfunction 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> |
Output:
2
Time Complexity: O(n * max(a, b))
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
