{x}
blog image

Number of Different Subsequences GCDs

You are given an array nums that consists of positive integers.

The GCD of a sequence of numbers is defined as the greatest integer that divides all the numbers in the sequence evenly.

  • For example, the GCD of the sequence [4,6,16] is 2.

A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.

  • For example, [2,5,10] is a subsequence of [1,2,1,2,4,1,5,10].

Return the number of different GCDs among all non-empty subsequences of nums.

 

Example 1:

Input: nums = [6,10,3]
Output: 5
Explanation: The figure shows all the non-empty subsequences and their GCDs.
The different GCDs are 6, 10, 3, 2, and 1.

Example 2:

Input: nums = [5,15,40,5,6]
Output: 7

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 2 * 105

Solution Explanation: Number of Different Subsequence GCDs

This problem asks to find the number of different greatest common divisors (GCD) among all non-empty subsequences of a given array nums. A brute-force approach of generating all subsequences and computing their GCDs would be extremely inefficient. The optimal solution leverages number theory and clever optimization.

Core Idea:

The solution cleverly avoids explicitly generating all subsequences. Instead, it iterates through possible GCD values and checks if each value can be the GCD of some subsequence. The key observation is that the maximum possible GCD is the maximum element in nums.

Algorithm:

  1. Find the maximum element: Determine the maximum value (mx) in the input array nums. This is the upper bound for any possible GCD.

  2. Create a set/boolean array: Create a set or boolean array (vis) to efficiently check if a number exists in nums. This speeds up the lookup process.

  3. Iterate through potential GCDs: Loop through numbers from 1 to mx. Each number x in this loop represents a potential GCD.

  4. Check for subsequences with GCD x: For each potential GCD x, iterate through its multiples (y). If a multiple y is present in nums (check using vis), then update the current GCD (g) using the GCD function (gcd(g, y)). If, at any point, g becomes equal to x, it means a subsequence with GCD x exists. We then increment the answer count (ans) and proceed to the next potential GCD.

  5. Return the count: After iterating through all potential GCDs, return the final count ans.

Time Complexity Analysis:

  • The outer loop iterates up to mx (the maximum element in nums).
  • The inner loop iterates through multiples of x, which in the worst case (x=1) would be up to mx. However, the inner loop will likely stop early once a subsequence with GCD x is found.

Therefore, the time complexity is approximately O(M log M), where M is the maximum value in nums. The gcd function has a logarithmic time complexity. The initialization of vis is O(n), where n is the length of nums. The overall time complexity is dominated by the nested loops.

Space Complexity Analysis:

The space complexity is O(M) due to the vis array (or set) which stores boolean values up to the maximum value in nums.

Code Implementation (Python):

import math
 
def gcd(a, b):
  if b == 0:
    return a
  return gcd(b, a % b)
 
def countDifferentSubsequenceGCDs(nums):
    mx = max(nums)
    vis = set(nums)
    ans = 0
    for x in range(1, mx + 1):
        g = 0
        for y in range(x, mx + 1, x):
            if y in vis:
                g = math.gcd(g, y)  # Use math.gcd for efficiency
                if g == x:
                    ans += 1
                    break
    return ans

Other languages (Java, C++, Go) would follow a similar structure, with appropriate adjustments for syntax and data structures. The core algorithmic idea remains the same.