Number of Different Subsequences GCDs

We need to find the number of different GCDs (Greatest Common Divisors) among all non-empty subsequences of the given array nums.

The idea here is to notice that there is no need to check all possible subsequences directly. Instead, we can leverage the mathematical properties of GCD to find the answer in an efficient manner.

Here’s a step-by-step approach:

  1. Find the Maximum Element: Determine the maximum element max_num in the array nums.
  2. Create a Frequency Table: Make a frequency table that counts the number of occurrences of each integer from 1 to max_num.
  3. Check Possible GCDs: Iterate from max_num down to 1 and check if each integer can be a GCD of some subsequence. Use the frequency table to check this by considering the multiples of each integer.
  4. Count Different GCDs: Count the number of different GCDs found in step 3.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

from math import gcd

class Solution:
    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
        max_num = max(nums)

        # Frequency table to count the occurrences of each number
        frequency = [0] * (max_num + 1)
        for num in nums:
            frequency[num] += 1

        # Function to check if x can be the GCD of some subsequence
        def can_be_gcd(x):
            current_gcd = 0
            # Check multiples of x
            for multiple in range(x, max_num + 1, x):
                # For each occurrence of the multiple, update the current_gcd
                for _ in range(frequency[multiple]):
                    current_gcd = gcd(current_gcd, multiple)
                    if current_gcd == x:
                        return True
            return False

        # Count the number of different GCDs
        count = 0
        for i in range(1, max_num + 1):
            if can_be_gcd(i):
                count += 1

        return count

The solution efficiently iterates through the possible GCDs, leveraging the mathematical properties of GCD, and checks if each one can be the GCD of some subsequence. It returns the count of different GCDs among all non-empty subsequences of nums.