Different Subsequences GCD

Hard
0/120
Average time to solve is 25m
profile
Contributed by
16 upvotes
Asked in company
American Express

Problem statement

You are given an array “ARR” of positive integers. Your task is to find the number of different GCD’s in all the non-empty subsequences of the given array.

Note:

The GCD of a list of numbers is defined as the greatest number that perfectly divides all the members of the given list. For example, the GCD of 6, 8, and 10 is 2.

A subsequence of the array is a list that can be made by using some elements of the given array. All the elements can also be part of a subsequence.

For example: the array [1, 2] has subsequences: [1], [2] and [1, 2]. Similarly for the array [1, 2, 3], one of the subsequences is [1, 3].
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’, which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains an integer ‘N’ denoting the size of the array.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of the array.
Output Format: 
For each test case, print the count of different GCD’s in all the non-empty subsequences of the given array.

Print the output of each test case in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^4
1 <= ARR[i] <= 10^5

Where ‘T’ is the number of test cases, ‘N’, denotes the size of the array 'ARR', and ‘ARR[i]’ denotes the elements of the array.

Time limit: 1 sec
Sample Input 1:
2
3
6 8 10
3
1 2 1
Sample Output 1:
4
2
Explanation For Sample Input 1:
In the first test case, 
The subsequences and their GCD’s are:
The different GCD’s from the above table are 6, 8, 10, 2. So, the answer is 4.    


In the second test case, 
The subsequences and their GCD’s are:
The different GCD’s from the above table are 1, 2. So, the answer is 2.

Sample Input 2:
2
4
5 10 15 20
3
2 5 10
Sample Output 2:
4
4
Explanation For Sample Input 1:
In the first test case, 
The different GCD’s are 5, 10, 15, 20. So, the answer is 4.

In the second test case, 
The different GCD’s are 1, 2, 5, 10. So, the answer is 4.
Hint

Can you think of creating all the subsequences?

Approaches (2)
Brute Force

Approach: The simple idea behind this approach is to find all possible values of gcd from the given array, store them in a hashMap and finally count the elements stored in the hashMap, which will be equal to the count of different GCD subsequences.

 

Algorithm:

 

  1. Initialize a hashMap to store all possible GCD values, let’s say 'RESULT'.
  2. Now, create a recursive function that will create all possible subsequences from the given array, let’s say 'GETSUBSEQUENCE'.
    • The recursive function will take ‘ARR’, the given array, “INDEX” initialized as ‘0’, and 'CURRENTGCD' initialized as ‘0’ as its parameters and calculate every possible gcd.
    • Calculate the gcd of ‘CURGCD’ and ‘ARR[INDEX]’ and store them in the ‘RESULT’ hashMap.
    • We will recursively call for two recursions:
      • One, including the current 'INDEX',
      • Second, excluding the current ‘INDEX’.
    • When the current “INDEX” is included, update the value of ‘CURRENTGCD’, else keep it the same.
  3. Finally, we will simply get the size of the 'RESULT' hashMap and return it.
Time Complexity

O(2 ^ N), where N is the size of the array.

 

Since we are recursively calling 2 times for every index, and the recursion depth is O(N) in the worst case. Hence, the overall Time Complexity is O(2 ^ N).

Space Complexity

O(N), where N is the size of the array.

 

Since we are using arrays to store GCD values, and the array will contain N elements, and also using the recursion stack, the overall Space Complexity is O(N).

Code Solution
(100% EXP penalty)
Different Subsequences GCD
Full screen
Console