Taro Logo

Number of Different Subsequences GCDs

Hard
Asked by:
Profile picture
11 views
Topics:
Arrays

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


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Does order inside a group not matter, so combinations of values are enough?
  2. Should every non-empty group be considered, including groups that hold a single number?
  3. Are duplicate values in the input the same number for the purpose of distinct divisors?
  4. Is one a valid result when the numbers in a group share no larger divisor?
  5. Can the largest value be used as the upper bound of the divisor search?

Brute Force Solution

Approach

This enumeration builds every non-empty combination of the values. For each combination it folds the numbers together with the Euclidean algorithm to get one greatest common divisor. A set records those divisors, and the answer is the size of the set.

Here's how the algorithm would work step-by-step:

  1. Prepare an empty set of divisors.
  2. Walk every combination size from one up through the full list length.
  3. For each combination, start the divisor at the first value.
  4. Fold each later value in by replacing the divisor with the greatest common divisor of the running value and that later value.
  5. Insert the finished divisor into the set.
  6. Skip the empty combination so that no zero divisor is recorded.
  7. Return how many distinct divisors were inserted.

Code Implementation

import math
from itertools import chain, combinations

def count_different_subsequence_gcds_brute_force(numbers):
    def calculate_gcd(first_number, second_number):
        while second_number:
            first_number, second_number = second_number, first_number % second_number
        return first_number

    def calculate_subsequence_gcd(subsequence):
        if not subsequence:
            return 0
        
        result_gcd = subsequence[0]
        for index in range(1, len(subsequence)):
            result_gcd = calculate_gcd(result_gcd, subsequence[index])
        return result_gcd

    # Generate all non-empty subsequences (or groupings) of the input numbers.
    all_subsequences = chain.from_iterable(combinations(numbers, r) for r in range(1, len(numbers) + 1))
    
    unique_gcd_values = set()
    
    # For each subsequence, we must compute its GCD to see if it's a new unique value.
    for current_subsequence in all_subsequences:
        gcd_of_subsequence = calculate_subsequence_gcd(list(current_subsequence))
        
        # A set is used to automatically handle duplicates, storing only the unique GCDs found.
        unique_gcd_values.add(gcd_of_subsequence)

    return len(unique_gcd_values)

Big(O) Analysis

Time Complexity
O(n * 2^n * log A) – There are two to the power of n non-empty combinations of an n-element list. A combination of size k performs k greatest-common-divisor steps. Summed over every combination, the element visits total n times two to the power of n minus one. Each Euclidean step is logarithmic in the size of the values. Multiplying those factors gives O(n * 2^n * log A), where A is the largest value.
Space Complexity
O(n + A) – The combination walk keeps only the group currently being folded, whose length is at most n, plus a call stack of that same depth. It does not store every combination at once. The set retains distinct divisors, and every divisor is an integer between one and the largest value. That set therefore holds at most A entries. The extra space is O(n + A).

Optimal Solution

Approach

This search asks, for every candidate divisor up to the largest value, whether some non-empty group has exactly that divisor. It looks only at multiples of the candidate that actually appear, and folds those multiples together. The candidate is counted when that fold lands back on the candidate itself.

Here's how the algorithm would work step-by-step:

  1. Put the values into a set for fast membership tests and remember the largest value.
  2. For each candidate from one through that largest value, start a running divisor at zero.
  3. Walk the multiples of the candidate from the candidate itself up through the largest value.
  4. When a multiple is present and the running divisor is still zero, set it to that multiple.
  5. When a later multiple is present, replace the running divisor by its greatest common divisor with that multiple.
  6. If the running divisor equals the candidate, count the candidate.
  7. Return the number of candidates that passed.

Code Implementation

def countDifferentSubsequenceGCDs(numbers):
    def calculate_gcd(first_number, second_number):
        while second_number:
            first_number, second_number = second_number, first_number % second_number
        return first_number

    # Convert the input list to a set for fast O(1) lookups.
    numbers_present = set(numbers)

    # The largest number in the set determines the upper bound for our search for possible GCDs.
    max_number_in_input = max(numbers)
    
    count_of_distinct_gcds = 0
    for potential_gcd in range(1, max_number_in_input + 1):
        gcd_of_multiples = 0

        # Find all multiples of the potential GCD that exist in the input numbers.
        for multiple in range(potential_gcd, max_number_in_input + 1, potential_gcd):
            if multiple in numbers_present:
                if gcd_of_multiples == 0:
                    gcd_of_multiples = multiple
                else:
                    gcd_of_multiples = calculate_gcd(gcd_of_multiples, multiple)

        # If the GCD of all found multiples equals our current potential GCD, it's a valid subsequence GCD.
        if gcd_of_multiples == potential_gcd:
            count_of_distinct_gcds += 1

    return count_of_distinct_gcds

Big(O) Analysis

Time Complexity
O(A log^2 A) – The outer loop tries every candidate up to the largest value A. For a candidate d, the inner loop visits every d-th integer up to A, which is about A divided by d visits. Summing A divided by d over every d is the harmonic series, which is on the order of A times the logarithm of A. Some of those visits also run the Euclidean algorithm, and each such step is logarithmic in A. The product is O(A log^2 A).
Space Complexity
O(n) – The membership set stores each distinct input value once, so it is at most linear in the list length. The scan keeps a candidate, a multiple, and a running divisor, all single numbers. No table of every possible divisor is allocated beyond the counter itself. The input list is not copied except through that set. Extra space is O(n).

Edge Cases

The list holds a single number
How to Handle:
Return one, because the only non-empty group contributes that number itself.
Every value is identical
How to Handle:
Count that number once, because every non-empty group has the same divisor.
The full set shares only one, but smaller groups share larger divisors
How to Handle:
Count both the shared divisors of the smaller groups and each number on its own.
One stored value divides another
How to Handle:
Count the smaller value when the multiples of it fold back to that same value.
The largest value is one
How to Handle:
Return one, because every non-empty group has divisor one.