Given an array of N numbers, the task is to count the number of subsequences that have gcd equal to 1.
Examples:
Input: a[] = {3, 4, 8, 16}
Output: 7
The subsequences are:
{3, 4}, {3, 8}, {3, 16}, {3, 4, 8},
{3, 4, 16}, {3, 8, 16}, {3, 4, 8, 16}
Input: a[] = {1, 2, 4}
Output: 4
A simple solution is to generate all subsequences or subsets. For every subsequence, check if its GCD is 1 or not. If 1, increment the result.
When we have values in the array (say all smaller than 1000), we can optimize the above solution as we know that number of possible GCDs would be small. We modify the recursive subset generation algorithm was considering two cases for every element, we either include or exclude it. We keep track of the current GCD and if we have already counted for this GCD, we return the count. So when we are considering a subset, some GCDs would appear again and again. Therefore the problem can be solved using Dynamic Programming. Given below are the steps to solve the above problem:
- Start from every index and call the recursive function by taking the index element.
- In the recursive function, we iterate till we reach N.
- The two recursive calls will be based on whether we take the index element or not.
- The base case will be to return 1 if we have reached the end and the gcd till now is 1.
- Two recursive calls will be func(ind+1, gcd(a[i], prevgcd)) and func(ind+1, prevgcd)
- The overlapping subproblems can be avoided by using the memoization technique.
Below is the implementation of the above approach:
C++
// C++ program to find the number// of subsequences with gcd 1#include <bits/stdc++.h>using namespace std;#define MAX 1000int gcd(int a, int b){ if (a == 0) return b; return gcd(b % a, a);}// Recursive function to calculate the number// of subsequences with gcd 1 starting with // particular indexint func(int ind, int g, int dp[][MAX], int n, int a[]){ // Base case if (ind == n) { if (g == 1) return 1; else return 0; } // If already visited if (dp[ind][g] != -1) return dp[ind][g]; // Either we take or we do not int ans = func(ind + 1, g, dp, n, a) + func(ind + 1, gcd(a[ind], g), dp, n, a); // Return the answer return dp[ind][g] = ans;}// Function to return the number of subsequencesint countSubsequences(int a[], int n){ // Hash table to memoize int dp[n][MAX]; memset(dp, -1, sizeof dp); // Count the number of subsequences int count = 0; // Count for every subsequence for (int i = 0; i < n; i++) count += func(i + 1, a[i], dp, n, a); return count;}// Driver Codeint main(){ int a[] = { 3, 4, 8, 16 }; int n = sizeof(a) / sizeof(a[0]); cout << countSubsequences(a, n); return 0;} |
Java
// Java program to find the number // of subsequences with gcd 1 class GFG{ static final int MAX = 1000; static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Recursive function to calculate the number // of subsequences with gcd 1 starting with // particular index static int func(int ind, int g, int dp[][], int n, int a[]) { // Base case if (ind == n) { if (g == 1) return 1; else return 0; } // If already visited if (dp[ind][g] != -1) return dp[ind][g]; // Either we take or we do not int ans = func(ind + 1, g, dp, n, a) + func(ind + 1, gcd(a[ind], g), dp, n, a); // Return the answer return dp[ind][g] = ans; } // Function to return the// number of subsequences static int countSubsequences(int a[], int n) { // Hash table to memoize int dp[][] = new int[n][MAX]; for(int i = 0; i < n; i++) for(int j = 0; j < MAX; j++) dp[i][j] = -1; // Count the number of subsequences int count = 0; // Count for every subsequence for (int i = 0; i < n; i++) count += func(i + 1, a[i], dp, n, a); return count; } // Driver Code public static void main(String args[]){ int a[] = { 3, 4, 8, 16 }; int n = a.length; System.out.println(countSubsequences(a, n)); }} // This code is contributed by Arnab Kundu |
Python3
# Python3 program to find the number # of subsequences with gcd 1 MAX = 1000def gcd(a, b): if (a == 0): return b return gcd(b % a, a)# Recursive function to calculate the # number of subsequences with gcd 1 # starting with particular index def func(ind, g, dp, n, a): # Base case if (ind == n): if (g == 1): return 1 else: return 0 # If already visited if (dp[ind][g] != -1): return dp[ind][g] # Either we take or we do not ans = (func(ind + 1, g, dp, n, a) + func(ind + 1, gcd(a[ind], g), dp, n, a)) # Return the answer dp[ind][g] = ans return dp[ind][g]# Function to return the number # of subsequences def countSubsequences(a, n): # Hash table to memoize dp = [[-1 for i in range(MAX)] for i in range(n)] # Count the number of subsequences count = 0 # Count for every subsequence for i in range(n): count += func(i + 1, a[i], dp, n, a) return count # Driver Code a = [3, 4, 8, 16 ] n = len(a)print(countSubsequences(a, n)) # This code is contributed by mohit kumar 29 |
C#
// C# program to find the number // of subsequences with gcd 1 using System;class GFG{static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Recursive function to calculate the number // of subsequences with gcd 1 starting with // particular index static int func(int ind, int g, int [][] dp, int n, int [] a) { // Base case if (ind == n) { if (g == 1) return 1; else return 0; } // If already visited if (dp[ind][g] != -1) return dp[ind][g]; // Either we take or we do not int ans = func(ind + 1, g, dp, n, a) + func(ind + 1, gcd(a[ind], g), dp, n, a); // Return the answer return dp[ind][g] = ans; } // Function to return the// number of subsequences static int countSubsequences(int [] a, int n) { // Hash table to memoize int [][] dp = new int[n][]; for(int i = 0; i < n; i++) for(int j = 0; j < 1000; j++) dp[i][j] = -1; // Count the number of subsequences int count = 0; // Count for every subsequence for (int i = 0; i < n; i++) count += func(i + 1, a[i], dp, n, a); return count; } // Driver Code public static void Main(){ int [] a = { 3, 4, 8, 16 }; int n = 4; int x = countSubsequences(a, n); Console.Write(x); }} // This code is contributed by // mohit kumar 29 |
PHP
<?php// PHP program to find the number // of subsequences with gcd 1 $GLOBALS['MAX'] = 1000;function gcd($a, $b) { if ($a == 0) return $b; return gcd($b % $a, $a); } // Recursive function to calculate the // number of subsequences with gcd 1 // starting with particular index function func($ind, $g, $dp, $n, $a) { // Base case if ($ind == $n) { if ($g == 1) return 1; else return 0; } // If already visited if ($dp[$ind][$g] != -1) return $dp[$ind][$g]; // Either we take or we do not $ans = func($ind + 1, $g, $dp, $n, $a) + func($ind + 1, gcd($a[$ind], $g), $dp, $n, $a); // Return the answer $dp[$ind][$g] = $ans; return $dp[$ind][$g] ;} // Function to return the number// of subsequences function countSubsequences($a, $n) { // Hash table to memoize $dp = array(array()) ; for($i = 0 ; $i < $n ; $i++) for($j = 0; $j < $GLOBALS['MAX']; $j++) $dp[$i][$j] = -1 ; // Count the number of subsequences $count = 0; // Count for every subsequence for ($i = 0; $i < $n; $i++) $count += func($i + 1, $a[$i], $dp, $n, $a); return $count; } // Driver Code $a = array(3, 4, 8, 16); $n = sizeof($a) ;echo countSubsequences($a, $n); // This code is contributed by Ryuga?> |
Javascript
<script>// JavaScript program to find the number // of subsequences with gcd 1 var MAX = 1000; function gcd(a , b) { if (a == 0) return b; return gcd(b % a, a); } // Recursive function to calculate the number // of subsequences with gcd 1 starting with // particular index function func(ind , g , dp , n , a) { // Base case if (ind == n) { if (g == 1) return 1; else return 0; } // If already visited if (dp[ind][g] != -1) return dp[ind][g]; // Either we take or we do not var ans = func(ind + 1, g, dp, n, a) + func(ind + 1, gcd(a[ind], g), dp, n, a); // Return the answer return dp[ind][g] = ans; } // Function to return the // number of subsequences function countSubsequences(a , n) { // Hash table to memoize var dp = Array(n).fill().map(()=>Array(MAX).fill(0)); for (i = 0; i < n; i++) for (j = 0; j < MAX; j++) dp[i][j] = -1; // Count the number of subsequences var count = 0; // Count for every subsequence for (i = 0; i < n; i++) count += func(i + 1, a[i], dp, n, a); return count; } // Driver Code var a = [ 3, 4, 8, 16 ]; var n = a.length; document.write(countSubsequences(a, n));// This code contributed by Rajput-Ji</script> |
Output
7
Complexity Analysis:
- Time Complexity: O(logN*N2), as we are recursively calling the function two times but we are using memorization and the GCD function will cost O(logN). Where N is the number of elements in the array.
- Auxiliary Space: O(N*1000), as we are using extra space for the DP matrix. Where N is the number of elements in the array.
Alternate Solution: Count the number of subsets of a set with GCD equal to a given number
Dynamic programming approach to this problem without memoization:
Basically, the approach will be making a 2d matrix in which i coordinate will be the position of elements of the given array and the j coordinate will be numbers from 0 to 100 ie. gcd can vary from 0 to 100 if array elements are not enough large. we will iterate on the given array and the 2d matrix will store information that till ith position that how many subsequences are there having gcd vary from 1 to 100. later on, we will add dp[i][1] to get all subsequences having gcd as 1.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// This function calculates // gcd of two numberint gcd(int a, int b){ if (b == 0) return a; return gcd(b, a % b);}// This function will return total// subsequencesint countSubsequences(int arr[], int n){ // Declare a dp 2d array long long int dp[n][101] = {0}; // Iterate i from 0 to n - 1 for(int i = 0; i < n; i++) { dp[i][arr[i]] = 1; // Iterate j from i - 1 to 0 for(int j = i - 1; j >= 0; j--) { if(arr[j] < arr[i]) { // Iterate k from 0 to 100 for(int k = 0; k <= 100; k++) { // Find gcd of two number int GCD = gcd(arr[i], k); // dp[i][GCD] is summation of // dp[i][GCD] and dp[j][k] dp[i][GCD] = dp[i][GCD] + dp[j][k]; } } } } // Add all elements of dp[i][1] long long int sum = 0; for(int i = 0; i < n; i++) { sum=(sum + dp[i][1]); } // Return sum return sum;}// Driver codeint main(){ int a[] = { 3, 4, 8, 16 }; int n = sizeof(a) / sizeof(a[0]); // Function Call cout << countSubsequences(a, n); return 0;} |
Java
// Java program for the// above approachimport java.util.*;class GFG{ // This function calculates // gcd of two numberstatic int gcd(int a, int b){ if (b == 0) return a; return gcd(b, a % b);}// This function will return total// subsequencesstatic long countSubsequences(int arr[], int n){ // Declare a dp 2d array long dp[][] = new long[n][101]; for(int i = 0; i < n; i++) { for(int j = 0; j < 101; j++) { dp[i][j] = 0; } } // Iterate i from 0 to n - 1 for(int i = 0; i < n; i++) { dp[i][arr[i]] = 1; // Iterate j from i - 1 to 0 for(int j = i - 1; j >= 0; j--) { if (arr[j] < arr[i]) { // Iterate k from 0 to 100 for(int k = 0; k <= 100; k++) { // Find gcd of two number int GCD = gcd(arr[i], k); // dp[i][GCD] is summation of // dp[i][GCD] and dp[j][k] dp[i][GCD] = dp[i][GCD] + dp[j][k]; } } } } // Add all elements of dp[i][1] long sum = 0; for(int i = 0; i < n; i++) { sum = (sum + dp[i][1]); } // Return sum return sum;}// Driver codepublic static void main(String args[]){ int a[] = { 3, 4, 8, 16 }; int n = a.length; // Function Call System.out.println(countSubsequences(a, n));}}// This code is contributed by bolliranadheer |
Python3
# Python3 program for the# above approach # This function calculates # gcd of two numberdef gcd(a, b): if (b == 0): return a; return gcd(b, a % b);# This function will return total# subsequencesdef countSubsequences(arr, n): # Declare a dp 2d array dp = [[0 for i in range(101)] for j in range(n)] # Iterate i from 0 to n - 1 for i in range(n): dp[i][arr[i]] = 1; # Iterate j from i - 1 to 0 for j in range(i - 1, -1, -1): if (arr[j] < arr[i]): # Iterate k from 0 to 100 for k in range(101): # Find gcd of two number GCD = gcd(arr[i], k); # dp[i][GCD] is summation of # dp[i][GCD] and dp[j][k] dp[i][GCD] = dp[i][GCD] + dp[j][k]; # Add all elements of dp[i][1] sum = 0; for i in range(n): sum = (sum + dp[i][1]); # Return sum return sum; # Driver codeif __name__=='__main__': a = [ 3, 4, 8, 16 ] n = len(a) # Function Call print(countSubsequences(a,n)) # This code is contributed by Pratham76 |
C#
// C# program for the above approachusing System;using System.Collections;using System.Collections.Generic; class GFG{ // This function calculates // gcd of two numberstatic int gcd(int a, int b){ if (b == 0) return a; return gcd(b, a % b);} // This function will return total// subsequencesstatic long countSubsequences(int []arr, int n){ // Declare a dp 2d array long [,]dp = new long[n, 101]; for(int i = 0; i < n; i++) { for(int j = 0; j < 101; j++) { dp[i, j] = 0; } } // Iterate i from 0 to n - 1 for(int i = 0; i < n; i++) { dp[i, arr[i]] = 1; // Iterate j from i - 1 to 0 for(int j = i - 1; j >= 0; j--) { if (arr[j] < arr[i]) { // Iterate k from 0 to 100 for(int k = 0; k <= 100; k++) { // Find gcd of two number int GCD = gcd(arr[i], k); // dp[i,GCD] is summation of // dp[i,GCD] and dp[j,k] dp[i, GCD] = dp[i, GCD] + dp[j, k]; } } } } // Add all elements of dp[i,1] long sum = 0; for(int i = 0; i < n; i++) { sum = (sum + dp[i, 1]); } // Return sum return sum;} // Driver codepublic static void Main(string []args){ int []a = { 3, 4, 8, 16 }; int n = a.Length; // Function Call Console.WriteLine(countSubsequences(a, n));}}// This code is contributed by rutvik_56 |
Javascript
<script>// javascript program for the// above approach // This function calculates // gcd of two number function gcd(a , b) { if (b == 0) return a; return gcd(b, a % b); } // This function will return total // subsequences function countSubsequences(arr , n) { // Declare a dp 2d array var dp = Array(n).fill().map(()=>Array(101).fill(0)); for (i = 0; i < n; i++) { for (j = 0; j < 101; j++) { dp[i][j] = 0; } } // Iterate i from 0 to n - 1 for (i = 0; i < n; i++) { dp[i][arr[i]] = 1; // Iterate j from i - 1 to 0 for (j = i - 1; j >= 0; j--) { if (arr[j] < arr[i]) { // Iterate k from 0 to 100 for (k = 0; k <= 100; k++) { // Find gcd of two number var GCD = gcd(arr[i], k); // dp[i][GCD] is summation of // dp[i][GCD] and dp[j][k] dp[i][GCD] = dp[i][GCD] + dp[j][k]; } } } } // Add all elements of dp[i][1] var sum = 0; for (i = 0; i < n; i++) { sum = (sum + dp[i][1]); } // Return sum return sum; } // Driver code var a = [ 3, 4, 8, 16 ]; var n = a.length; // Function Call document.write(countSubsequences(a, n));// This code contributed by aashish1995</script> |
Output
7
Complexity Analysis:
- Time Complexity: O(100*logN*N2), as we are using nested loops and the GCD function will cost O(logN). Where N is the number of elements in the array.
- Auxiliary Space: O(N*100), as we are using extra space for the DP matrix. Where N is the number of elements in the array.
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!
