# Number of Different Subsequences GCDs in Java

In this tutorial, we are going to learn about number of different subsequences GCDs in Java. Finding all feasible different Greatest Common Divisors (GCDs) among every non-empty subsequences of an array array[] made up of N positive integers is the task at hand.

Examples:

Example 1:

Input: array[] = {2, 6, 9}
Output: 1 2 3 6 9
Explanation:
The non-empty subsequences possible are {2}, {6}, {9}, {2, 6}, {6, 9}, {2, 9}, {2, 6, 9} and their corresponding GCDs are 2, 6, 9, 2, 3, 1, 1.
Therefore, print all the GCDs as {1, 2, 3, 6, 9}.

Example 2:

Input: array[] = {4, 5, 10}

Output: 1 2 4 5 10

Explanation:

The non-empty subsequences possible are {4}, {5}, {10}, {4, 5}, {5, 10}, {4, 10}, {4, 5, 10} and their corresponding GCDs are 4, 5, 10, 1, 5, 2, 1.

Therefore, print all the GCDs as {1, 2, 4, 5, 10}.

Example 3:

Input: array[] = {7, 14, 21}

Output: 7 14 21

Explanation:

The non-empty subsequences possible are {7}, {14}, {21}, {7, 14}, {14, 21}, {7, 21}, {7, 14, 21} and their corresponding GCDs are 7, 14, 21, 7, 7, 7, 7.

Therefore, print all the GCDs as {7, 14, 21}.

Example 4:

Input: array[] = {6, 15, 24}

Output: 1 3 6 15 24

Explanation:

The non-empty subsequences possible are {6}, {15}, {24}, {6, 15}, {15, 24}, {6, 24}, {6, 15, 24} and their corresponding GCDs are 6, 15, 24, 3, 3, 6, 3.

Therefore, print all the GCDs as {1, 3, 6, 15, 24}.

Example 5:

Input: array[] = {5, 10, 20}

Output: 5 10 20

Explanation:

The non-empty subsequences possible are {5}, {10}, {20}, {5, 10}, {10, 20}, {5, 20}, {5, 10, 20} and their corresponding GCDs are 5, 10, 20, 5, 10, 5, 5.

Therefore, print all the GCDs as {5, 10, 20}.

## Approach 1: Using brute force algorithm

### ALGORITHM:

Step 1: Establish the range of possible GCD values by figuring out the array's maximum entry.

Step 2: Determine whether a given prospective GCD number can represent the GCD of any subsequence.

Step 3: Consider only those items that divide by the anticipated GCD value as of right now.

Step 4: For the current set of divisible items, use the auxiliary method findGCD to determine the GCD.

Step 5: Print the quantity of distinct GCDs for the supplied input arrays.

Filename: DifferentSubsequencesGCD.java

`import java.util.ArrayList; import java.util.Set; import java.util.HashSet; public class DifferentSubsequencesGCD  {     ArrayList<ArrayList<Integer>> arraylist = new ArrayList<ArrayList<Integer>>();     Set<Integer> uniqueGCD = new HashSet<Integer>();     public void calculateSubsequences(int array[],  int n,  int a,  ArrayList<Integer> temp)      {         if(a >= n)         {             // increasing the 2-d array list's element count            ArrayList<Integer> tempSubsequence = new ArrayList<Integer>();             for(int index = 0; index < temp.size(); index++)             {                 tempSubsequence.add(temp.get(index));             }             arraylist.add(tempSubsequence);             return;         }         temp.add(array[a]);         // containing the items in the temporary subarray list        calculateSubsequences(array,  n,  a + 1,  temp);         int idx = temp.size() - 1;         temp.remove(idx);         // disregarding the contents of the temporary subarray list        calculateSubsequences(array,  n,  a + 1,  temp);     }     // technique for recursively determining the GCD of the two // integers a1 and a2    public int calculateGCD(int p1,  int p2)     {         if(p1 == 0)         {             return p2;         }         // calculating the GCD of two numbers,  p1 and p2,  recursively        return calculateGCD(p2 % p1,  p1);     }     public void calculateGCDSubSequence(ArrayList<Integer> arraylistl1)     {         // There is no need to locate the GCD if the array list is empty.        if(arraylistl1.size() == 0)         {             return;         }         // The GCD is regarded as the element itself when there is only one element in the array list.        if(arraylistl1.size() == 1)         {             uniqueGCD.add(arraylistl1.get(0));             return;         }         int g1 = arraylistl1.get(0);         int g2 = arraylistl1.get(1);         int g = calculateGCD(g1,  g2);         for(int a = 2; a < arraylistl1.size(); a++)         {             g = calculateGCD(g,  arraylistl1.get(a));         }         uniqueGCD.add(g);     }     public void calculateGCDs()     {         int n = arraylist.size();         for(int a = 0; a < n; a++)         {             calculateGCDSubSequence(arraylist.get(a));         }     }     public static void main(String argvs[])     {         // constructing an object with the DiffSubseqGCD class        DifferentSubsequencesGCD object = new DifferentSubsequencesGCD();         // sample 1         int inArray[] = {7,  5,  3};         int n = inArray.length;         ArrayList<Integer> temp = new ArrayList<Integer>();         object.calculateSubsequences(inArray,  n,  0,  temp);         object.calculateGCDs();         System.out.println("For the given input array:  ");         for(int a = 0; a < n; a++)         {             System.out.print(inArray[a] + " ");         }         System.out.println();         System.out.println("The total number of unique GCDs is:  " + object.uniqueGCD.size());         System.out.println();         object.uniqueGCD = new HashSet<Integer>();         object.arraylist = new ArrayList<ArrayList<Integer>>();         // sample 2         int inArray1[] = {6,  12,  18};         n = inArray1.length;         temp = new ArrayList<Integer>();         object.calculateSubsequences(inArray1,  n,  0,  temp);         object.calculateGCDs();         System.out.println("For the given input array:  ");         for(int a = 0; a < n; a++)         {             System.out.print(inArray1[a] + " ");         }         System.out.println();         System.out.println("The total number of unique GCDs is:  " + object.uniqueGCD.size());     } }`

Output:

`For the given input array: 7 5 3The total number of unique GCDs is:  4For the given input array: 6 12 18The total number of unique GCDs is:  3`

Complexity analysis:

Two further recursive calls follow each recursive call. As a result, the program's temporal complexity is exponential. Additionally, the program's space complexity is exponential.

The program mentioned above has too much time and space complexity, making it unsuitable for larger inputs. Consequently, in order to lower the time complexity and space complexity, some optimization is required.

## Approach 2: Using greedy algorithm

### ALGORITHM:

Step 1: determine the various GCDs for the supplied array's subsequence.

Step 2: Keep the HashSet filled with all of the array entries.

Step 3: Using the variable i, iterate across the range [1, M] and carry out the subsequent actions:
Go through each of i's multiples one by one. If a multiple of i is found in the HashSet, output the current element i as a potential GCD.

Filename: NumberOfSubsequences.java

`import java.util.*;public class NumberOfSubsequences{static int gcd1(int x, int y){            return y == 0 ? x : gcd1(y, x % y);}// Function to determine each GCD for the provided array's subsequencestatic void calculateGCDsSubsequence(ArrayList<Integer> array){            ArrayList<Integer> result = new ArrayList<Integer>();            HashSet<Integer> set = new HashSet<Integer>();            for(int a : array)                        set.add(a);            int X = Integer.MIN_VALUE;            for(int a : array)            {                        if (a > X)                                    X = a;            }            for(int a = 1; a <= X; a++)            {                        int gcd = 0;                        // Determine if a can be the GCD of any subsequence                        for(int b = a; b < X + 1; b += a)                        {                                    if (set.contains(b))                                                gcd = gcd1(gcd, b);                        }                        if (gcd == a)                                    result.add(a);            }            for(int a = 0; a < result.size(); a++)            System.out.print(result.get(a) + " ");}public static void main(String args[]){            ArrayList<Integer> array = new ArrayList<Integer>();            array.add(7);            array.add(5);            array.add(3);            calculateGCDsSubsequence(array);}}`

Output:

`1 3 5 7`

Time complexity: The time complexity of the program is O(M*log M).

Space complexity: The space complexity of the program is O(N).

## Approach 3: Using divisor based GCD identification

### ALGORITHM:

Step 1: Make a HashSet out of the input array for quick and easy searching.

Step 2: Determine the array's maximum element to establish the range of possible GCD values.

Step 3: Verify that the array has all multiples of each feasible GCD value, ranging from 1 to the highest element.

Filename: DifferentSubsequencesGCD1.java

`import java.util.ArrayList; import java.util.Set; import java.util.HashSet; public class DifferentSubsequenceGCD1  { public int calculateGCD(int x1,  int x2) { if(x1 == 0) { return x2; } // computing the GCD of two numbers,  x1 and x2,  recursivelyreturn calculateGCD(x2 % x1,  x1); } public int calculateGCDsSubsequence(ArrayList<Integer> arraylist) { ArrayList<Integer> result = new ArrayList<Integer>(); HashSet<Integer> hashset = new HashSet<Integer>(); for(int a = 0; a < arraylist.size(); a++) { hashset.add(arraylist.get(a)); } int Maximum = Integer.MIN_VALUE; for(int a = 0; a < arraylist.size(); a++)  { if (arraylist.get(a) > Maximum) { Maximum = arraylist.get(a); } }    for(int b = 1; b <= Maximum; b++) { int computeGCD = 0; for(int c = b; c < Maximum + 1; c += b) { if (hashset.contains(c)) { computeGCD = calculateGCD(computeGCD,  c); } } if (computeGCD == b) { result.add(b); } } return result.size(); } public static void main(String argvs[]) { // making an item in the DiffSubseqGCD1 classDifferentSubsequenceGCD1 object = new DifferentSubsequenceGCD1(); // sample 1 ArrayList<Integer> arraylist = new ArrayList<Integer>(); arraylist.add(7); arraylist.add(5); arraylist.add(3); int n = arraylist.size(); int result = object.calculateGCDsSubsequence(arraylist); System.out.println("For the given input array:  "); for(int a = 0; a < n; a++) { System.out.print(arraylist.get(a) + " "); } System.out.println(); System.out.println("The total number of unique GCDs is:  " + result); System.out.println(); // sample 2 ArrayList<Integer> arraylist1 = new ArrayList<Integer>(); arraylist1.add(6); arraylist1.add(8); arraylist1.add(10); n = arraylist1.size(); result = object.calculateGCDsSubsequence(arraylist1); System.out.println("For the given input array:  "); for(int a = 0; a < n; a++) { System.out.print(arraylist1.get(a) + " "); } System.out.println(); System.out.println("The total number of unique GCDs is:  " + result); } }`

Output:

`For the given input array: 7 5 3The total number of unique GCDs is:  4For the given input array: 6 8 10The total number of unique GCDs is:  4`

Complexity analysis:

The program has an O(Max * log(Max)) time complexity, where Max is the array's maximum element. O(N), where N is the total number of entries in the array list, is the program's space complexity.