We are given an array of positive integers and an integer k. Find the maximum possible GCD of a subsequence of size k.
Examples:
Input : arr[] = [2, 1, 4, 6] k = 3 Output : 2 GCD of [2, 4, 6] is 2 Input : arr[] = [1, 2, 3] k = 3 Output : 1 GCD of [1, 2, 3] is 1
Method 1 Generate all the subsequences of size k one by one and then find the GCD of all such generated subsequences. Print the largest found GCD.
Method 2 In this method, we maintain a count array to store the count of divisors of every element. We will traverse the given array and for every element, we will calculate its divisors and increment at the index of the count array. The process of computing divisors will take O(sqrt(arr[i])) time, where arr[i] is element in the given array at index i. After the whole traversal, we can simply traverse the count array from the last index to index 1. If we find an index with a value equal to or greater than k, then this means that it is a divisor of at least k elements and also the max GCD.
Steps to solve this problem:
1. declare a variable and store maximum element of the array in it.
2. declare an array divisors of size high+1 and initialize it with 0.
3. iterate through i=0 till n:
*iterate through j=1 till sqrt(arr[i]):
*check if arr[i]%j is equal to 0 than divisors[j]++ and divisors[arr[i]/j]++ if j is not equal to arr[i]/j.
4. iterate through i=high till i>=1:
*check if divisors[i]>=k than return i.
Implementation:
C++
// CPP program to find subsequence of size // k with maximum possible GCD. #include <bits/stdc++.h> using namespace std; // function to find GCD of sub sequence of // size k with max GCD in the array int findMaxGCD(int arr[], int n, int k) { // Computing highest element int high = *max_element(arr, arr+n); // Array to store the count of divisors // i.e. Potential GCDs int divisors[high + 1] = { 0 }; // Iterating over every element for (int i = 0; i < n; i++) { // Calculating all the divisors for (int j = 1; j <= sqrt(arr[i]); j++) { // Divisor found if (arr[i] % j == 0) { // Incrementing count for divisor divisors[j]++; // Element/divisor is also a divisor // Checking if both divisors are // not same if (j != arr[i] / j) divisors[arr[i] / j]++; } } } // Checking the highest potential GCD for (int i = high; i >= 1; i--) // If this divisor can divide at least k // numbers, it is a GCD of at least one // sub sequence of size k if (divisors[i] >= k) return i; } // Driver code int main() { // Array in which sub sequence with size // k with max GCD is to be found int arr[] = { 1, 2, 4, 8, 8, 12 }; int k = 3; int n = sizeof(arr) / sizeof(arr[0]); cout << findMaxGCD(arr, n, k); return 0; } |
Java
// Java program to find // subsequence of size // k with maximum possible GCD import java .io.*; import java .util.*; class GFG { // function to find GCD of // sub sequence of size k // with max GCD in the array static int findMaxGCD(int []arr, int n, int k) { Arrays.sort(arr); // Computing highest element int high = arr[n - 1]; // Array to store the // count of divisors // i.e. Potential GCDs int []divisors = new int[high + 1]; // Iterating over // every element for (int i = 0; i < n; i++) { // Calculating all the divisors for (int j = 1; j <= Math.sqrt(arr[i]); j++) { // Divisor found if (arr[i] % j == 0) { // Incrementing count // for divisor divisors[j]++; // Element/divisor is // also a divisor Checking // if both divisors are // not same if (j != arr[i] / j) divisors[arr[i] / j]++; } } } // Checking the highest // potential GCD for (int i = high; i >= 1; i--) // If this divisor can divide // at least k numbers, it is // a GCD of at least one sub // sequence of size k if (divisors[i] >= k) return i; return 0 ; } // Driver code static public void main (String[] args) { // Array in which sub sequence // with size k with max GCD is // to be found int []arr = { 1, 2, 4, 8, 8, 12 }; int k = 3; int n = arr.length; System.out.println(findMaxGCD(arr, n, k)); } } // This code is contributed // by anuj_67. |
Python 3
# Python 3 program to find subsequence # of size k with maximum possible GCD. import math # function to find GCD of sub sequence # of size k with max GCD in the array def findMaxGCD(arr, n, k): # Computing highest element high = max(arr) # Array to store the count of # divisors i.e. Potential GCDs divisors = [0] * (high + 1) # Iterating over every element for i in range(n) : # Calculating all the divisors for j in range(1, int(math.sqrt(arr[i])) + 1): # Divisor found if (arr[i] % j == 0) : # Incrementing count for divisor divisors[j] += 1 # Element/divisor is also a divisor # Checking if both divisors are # not same if (j != arr[i] // j): divisors[arr[i] // j] += 1 # Checking the highest potential GCD for i in range(high, 0, -1): # If this divisor can divide at least k # numbers, it is a GCD of at least one # sub sequence of size k if (divisors[i] >= k): return i # Driver code if __name__ == "__main__": # Array in which sub sequence with size # k with max GCD is to be found arr = [ 1, 2, 4, 8, 8, 12 ] k = 3 n = len(arr) print(findMaxGCD(arr, n, k)) # This code is contributed by ita_c |
C#
// C# program to find subsequence of size // k with maximum possible GCD using System; using System.Linq; public class GFG { // function to find GCD of sub sequence of // size k with max GCD in the array static int findMaxGCD(int []arr, int n, int k) { // Computing highest element int high = arr.Max(); // Array to store the count of divisors // i.e. Potential GCDs int []divisors = new int[high+1]; // Iterating over every element for (int i = 0; i < n; i++) { // Calculating all the divisors for (int j = 1; j <= Math.Sqrt(arr[i]); j++) { // Divisor found if (arr[i] % j == 0) { // Incrementing count for divisor divisors[j]++; // Element/divisor is also a divisor // Checking if both divisors are // not same if (j != arr[i] / j) divisors[arr[i] / j]++; } } } // Checking the highest potential GCD for (int i = high; i >= 1; i--) // If this divisor can divide at least k // numbers, it is a GCD of at least one // sub sequence of size k if (divisors[i] >= k) return i; return 0 ; } // Driver code static public void Main () { // Array in which sub sequence with // size k with max GCD is to be found int []arr = { 1, 2, 4, 8, 8, 12 }; int k = 3; int n = arr.Length; Console.WriteLine(findMaxGCD(arr, n, k)); } } // This code is contributed by anuj_67. |
Javascript
<script> // Javascript program to find // subsequence of size // k with maximum possible GCD // function to find GCD of // sub sequence of size k // with max GCD in the array function findMaxGCD(arr,n,k) { arr.sort(function(a,b){return a-b;}); // Computing highest element let high = arr[n - 1]; // Array to store the // count of divisors // i.e. Potential GCDs let divisors = new Array(high + 1); for(let i=0;i<divisors.length;i++) { divisors[i]=0; } // Iterating over // every element for (let i = 0; i < n; i++) { // Calculating all the divisors for (let j = 1; j <= Math.sqrt(arr[i]); j++) { // Divisor found if (arr[i] % j == 0) { // Incrementing count // for divisor divisors[j]++; // Element/divisor is // also a divisor Checking // if both divisors are // not same if (j != Math.floor(arr[i] / j)) divisors[(Math.floor(arr[i] / j))]++; } } } // Checking the highest // potential GCD for (let i = high; i >= 1; i--) // If this divisor can divide // at least k numbers, it is // a GCD of at least one sub // sequence of size k if (divisors[i] >= k) return i; return 0 ; } // Driver code let arr=[1, 2, 4, 8, 8, 12]; let k = 3; let n = arr.length; document.write(findMaxGCD(arr, n, k)); // This code is contributed by rag2127 </script> |
Output
4
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!
