Last Updated: 15 Apr, 2021

Different Subsequences GCD

Hard

Asked in company

Solve now

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].

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

Solve now

Approaches

01 Approach

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:

Initialize a hashMap to store all possible GCD values, let’s say 'RESULT'.
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.
Finally, we will simply get the size of the 'RESULT' hashMap and return it.

Solve now

02 Approach

Approach: The basic idea behind this approach is to check values from 1 to the maximum element as we know that the GCD of any number of the array can not be bigger than the maximum element. We will also use the property that GCD of multiples of a number is the number itself.

For example:

The GCD of 5 and 10 is 5, similarly if we add another multiple of 5 in the list. i.e GCD of 5, 10, and 15 is still 5, and it remains 5 till we are adding multiples of 5 to the list. This is true for any value and its multiples.

So, in short, we will traverse through all possible GCD options, check for its multiples, and increment if we find the current calculated GCD equal to the GCD options.

Algorithm:

Initialize 'ANS' with value = 0, which will store the count of different subsequence GCD’s.
Initialize ‘MAXVALUE’ as 0 to store the current maximum value.
Initialize an array 'CHECK' with all values 0 to keep track if the number is present in the array or not.
Start traversing the array and find the maximum element let’s say ‘MAXVALUE’.
- Update 'CHECK' as 1, to understand it has been found or already worked upon.
Start traversing to check all possible values that can be the GCD, in simple words traverse through 'i' = 1 to ‘MAXVALUE’.
- Initialize 'CURRENTGCD' with value = 0 to store the current GCD.
- Start traversing for all multiples of ‘i’, i.e from ‘j’ = i to 'j' <= ‘MAXVALUE’ and incrementing by 'i' after each traversal
  - If ‘j’ is found in the 'CHECK' array
    - Update ‘CURRENTGCD’ as GCD of ‘CURRENTGCD’ and ‘j’
  - If 'CURRENTGCD' is equal to i, that checks if we can form a subsequence with the GCD
    - Increment 'ANS' and then break.
Finally, return 'ANS'.

Solve now