Maximize GCD of an array by increments or decrements by K
Given an array arr[] consisting of N positive integers and a positive integer K, the task is to maximize the GCD of the array arr[] by either increasing or decreasing any array element by K.
Examples:
Input: arr[] = {3, 9, 15, 24}, K = 1
Output: 4
Explanation:
Perform the following operations on the array arr[]:
Increment arr[0] by 1. Therefore, arr[] modifies to {4, 9, 15, 24}.
Decrement arr[1] by 1. Therefore, arr[] modifies to {4, 8, 15, 24}.
Increment arr[2] by 1. Therefore, arr[] modifies to {4, 8, 16, 24}.
Therefore, GCD of the modified array is 4.Input: arr[] = {5, 9, 2}, K = 1
Output: 3
Naive Approach: The simplest approach to solve this problem is to consider all three options for each array element arr[i], i.e., increase arr[i] by K, decrease arr[i] by K or neither increment nor decrement arr[i]. Generate the arrays formed in all the 3 cases using recursion and print the maximum of GCD of all the arrays obtained.
Time Complexity: O(3N)
Auxiliary Space: O(1)
Another Approach: The above approach can be optimized using Dynamic Programming. Follow the steps below to solve the given problem:
- Initialize an auxiliary array, say dp[][3], where dp[i][0], dp[i][1], and dp[i][2] denotes the maximum GCD possible upto ith index by not changing the ith elements, incrementing or decrementing the ith element by K respectively.
- Fill the first row of dp[][3] by updating dp[0][0], dp[0][1] and dp[0][2] with arr[0], arr[0] + K and arr[0] ā K respectively.
- Iterate over the range [1, N ā 1] and perform the following steps:
- For dp[i][0], find the maximum GCD of A[i] with 3 previous states, i.e., dp[i ā 1][0], dp[i ā 1][1] and dp[i ā 1][2] once at a time, and store the maximum result in dp[i][0].
- Similarly, store the results in dp[i][1] and dp[i][2] by taking (arr[i] + K) and (arr[i] ā K) respectively.
- After completing the above steps, print the maximum value in the row dp[N ā 1] as the result.
Below is the implementation of the above approach:
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
Time Complexity: O(N*log(M)), where M is the smallest element in the array arr[]
Auxiliary Space: O(N)
Efficient approach :
In this approach we use 1D array and one less iteration to find the solution below are the implementation steps of this approach.
Steps to solve this problem :
- Initialize a dp table of size 3 named ādpā and set all its values to zero using the āmemsetā function.
- Traverse the array A[] over indices [1, N ā 1].
- For each element in the array A[], store the previous state results in variables x, y, and z.
- For each current state, store the maximum GCD result by calling the āfindGCDā function for all three possibilities ā not changing the element, incrementing the element by K, and decrementing the element by K.
- Store the required result in a variable named āmxā by finding the maximum of the dp table values and 3.
- Return the result stored in āmxā.
Implementation :
C++
// C++ program for 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 3 int dp[3]; memset (dp, 0, sizeof (dp)); // Base Cases: // If only one element is present dp[0] = A[0]; dp[1] = A[0] + K; dp[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[0]; int y = dp[1]; int z = dp[2]; // Store maximum GCD result // for each current state dp[0] = findGCD(x, y, z, A[i]); dp[1] = findGCD(x, y, z, A[i] + K); dp[2] = findGCD(x, y, z, A[i] - K); } // Store the required result int mx = max({ 3, dp[0], dp[1], dp[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; } // this code is contributed by bhardwajji |
Java
import java.io.*; import java.lang.*; import java.util.*; class Main { // 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 3 int dp[] = new int [ 3 ]; Arrays.fill(dp, 0 ); // Base Cases: // If only one element is present dp[ 0 ] = A[ 0 ]; dp[ 1 ] = A[ 0 ] + K; dp[ 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[ 0 ]; int y = dp[ 1 ]; int z = dp[ 2 ]; // Store maximum GCD result // for each current state dp[ 0 ] = findGCD(x, y, z, A[i]); dp[ 1 ] = findGCD(x, y, z, A[i] + K); dp[ 2 ] = findGCD(x, y, z, A[i] - K); } // Store the required result int mx = Math.max(dp[ 0 ], Math.max(dp[ 1 ], dp[ 2 ])); // Return the result return mx; } // Driver Code public static void main(String[] args) throws java.lang.Exception { int arr[] = { 3 , 9 , 15 , 24 }; int K = 1 ; int N = arr.length; System.out.println(maximumGCD(arr, N, K)); } // Function to calculate GCD of two numbers static int gcd( int a, int b) { if (b == 0 ) { return a; } return gcd(b, a % b); } } |
Python3
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 3 dp = [ 0 ] * 3 # Base Cases: # If only one element is present dp[ 0 ] = A[ 0 ] dp[ 1 ] = A[ 0 ] + K dp[ 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[ 0 ] y = dp[ 1 ] z = dp[ 2 ] # Store maximum GCD result # for each current state dp[ 0 ] = findGCD(x, y, z, A[i]) dp[ 1 ] = findGCD(x, y, z, A[i] + K) dp[ 2 ] = findGCD(x, y, z, A[i] - K) # Store the required result mx = max ( 3 , dp[ 0 ], dp[ 1 ], dp[ 2 ]) # Return the result return mx # Driver Code arr = [ 3 , 9 , 15 , 24 ] K = 1 N = len (arr) print (maximumGCD(arr, N, K)) |
C#
using System; public class GFG { // 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; } static int gcd( int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } // 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 3 int [] dp = new int [3]; Array.Fill(dp, 0); // Base Cases: // If only one element is present dp[0] = A[0]; dp[1] = A[0] + K; dp[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[0]; int y = dp[1]; int z = dp[2]; // Store maximum GCD result // for each current state dp[0] = findGCD(x, y, z, A[i]); dp[1] = findGCD(x, y, z, A[i] + K); dp[2] = findGCD(x, y, z, A[i] - K); } // Store the required result int mx = Math.Max(Math.Max(dp[0], dp[1]), Math.Max(dp[2], 3)); // 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.WriteLine(maximumGCD(arr, N, K)); } } |
Javascript
// Function to return the maximum GCD // by taking each operation function findGCD(x, y, z, res) { // Store the maximum GCD obtained // by either incrementing, decrementing // or not changing A[i] let 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 3 const dp = new Array(3).fill(0); // Base Cases: // If only one element is present dp[0] = A[0]; dp[1] = A[0] + K; dp[2] = A[0] - K; // Traverse the array A[] over indices [1, N - 1] for (let i = 1; i < N; i++) { // Store the previous state results const x = dp[0]; const y = dp[1]; const z = dp[2]; // Store maximum GCD result // for each current state dp[0] = findGCD(x, y, z, A[i]); dp[1] = findGCD(x, y, z, A[i] + K); dp[2] = findGCD(x, y, z, A[i] - K); } // Store the required result const mx = Math.max(3, dp[0], dp[1], dp[2]); // Return the result return mx; } // Driver Code const arr = [3, 9, 15, 24]; const K = 1; const N = arr.length; console.log(maximumGCD(arr, N, K)); function gcd(a, b) { if (b === 0) { return a; } return gcd(b, a % b); } |
4
Time Complexity: O(N)
Auxiliary Space: O(N)