1819. Number of Different Subsequences GCDs

Problem Description

In this problem, you are given an array of positive integers called nums. You are asked to calculate the number of different Greatest Common Divisors (GCDs) that can be obtained from all possible non-empty subsequences of the array.

The term GCD refers to the largest integer that can evenly divide all the numbers in a sequence. For instance, the GCD of the sequence [4,6,16] is 2, since 2 is the greatest integer that can divide 4, 6, and 16 without leaving a remainder.

A subsequence is defined as a sequence that can be derived from the array by removing some elements (or potentially no elements at all). For example, [2,5,10] is a subsequence of [1,2,1,2,4,1,5,10].

The goal is to determine how many distinct GCDs you can find among all non-empty subsequences of the nums array.

Intuition

The solution is based on the insight that to find the GCD of a sequence, one does not necessarily need to consider all elements of the sequence; it's enough to consider only those elements that are multiples of a potential GCD candidate.

To employ this insight, we iterate over all integers x from 1 up to the maximum number in nums, considering each x as a potential GCD. For each potential GCD x, we want to find if there's a subsequence of nums whose GCD is exactly x. We do this by iterating through all multiples of x up to the maximum number in nums and calculating their GCD. If at any point our calculated GCD equals x, we know that we've found a subsequence whose GCD is x, and we count that.

In more detail, we follow these steps:

1. Find the maximum number in nums. This bounds the largest possible GCD.
2. Create a visibility set vis that contains all numbers present in nums to allow for O(1) lookups.
3. Initialize a counter ans to keep track of how many different GCDs we have found.
4. Iterate over each integer x starting from 1 up to the maximum number (inclusive). For each x, iterate through its multiples.
5. If a multiple y of x is in vis, calculate the GCD of y and the current GCD value g.
6. As soon as the GCD equals x, increment the counter ans and stop considering further multiples of x since we have found a valid subsequence for this GCD.
7. Return the counter ans, which now contains the number of distinct GCDs.

By doing this, we systematically check each number as a potential GCD and use the presence of its multiples in nums to see if that number is the GCD of some subsequence. With this approach, we are able to arrive at the solution efficiently.

Learn more about Math patterns.

Solution Approach

The implementation of the solution uses the mathematical concept of the Greatest Common Divisor (GCD) and some basic set operations for efficient lookup. The general approach involves iterating over all possible GCD values, checking for their existence by examining the multiples within the given nums array, and calculating the actual GCD. Here is a deeper dive into the approach:

1. Calculate the Maximum Value (mx): Determine the maximum value in the nums array, which sets a bound for the largest possible GCD.

2. Visibility Set (vis): Convert the nums array into a set. This vis set allows for constant-time complexity (O(1)) checks to determine if a multiple of the current GCD candidate x is in the nums array.

3. GCD Function: The built-in gcd function from Python's [math](/problems/math-basics) module is used to compute the Greatest Common Divisor of two numbers.

4. Iterate Over Potential GCDs (x): For every integer x from 1 to mx, perform the following:

   • Initialize a variable g to 0, which will store the current GCD as we iterate through the multiples of x.
   • Loop through each multiple of x—y—starting from x to mx (inclusive) and incremented by x. We only need to consider multiples of x because a GCD will always have to be a factor of the numbers in the subsequence.

5. Check Multiples and Calculate GCD:

   • If the multiple y is present in the vis set, compute the GCD of the current GCD value g and y. This GCD represents the GCD of the subsequence consisting of the multiples of x encountered so far. As such, g is incrementally updated to always reflect the GCD of this growing subsequence.
   • If at any point g becomes equal to x, it means we've found a subsequence whose GCD is the current candidate x. When this happens, increment the counter ans by 1 to signify that another unique GCD has been found.
   • Break out of the loop for multiples of x because we've accomplished our goal for the current GCD candidate x. Continuing the loop would be redundant since we only count distinct GCDs.

6. Return Result: After going through all integers from 1 to mx, the counter ans holds the number of different GCDs. Returning ans completes the implementation and gives us the desired result.

The time complexity of the solution comes down to the number of iterations we perform, which depends on the range of numbers (mx) and the number of divisors they have. By using a set for lookups and the efficient gcd function, the implementation maintains acceptable performance for the given constraints.

Example Walkthrough

Let's consider a simple example to illustrate the solution approach. We will use the array nums = [3, 6, 12].

Here's a step-by-step walkthrough using the provided solution approach:

1. Calculate the Maximum Value (mx): The maximum value in the nums array is 12.

2. Visibility Set (vis): Convert the array to a set: vis = {3, 6, 12}.

3. GCD Function: We will use Python's built-in math.gcd function to compute the Greatest Common Divisor.

4. Iterate Over Potential GCDs (x): We iterate over each integer from 1 to 12 (inclusive). Let's take a few iterations as an example:

   • For x = 1:
     • Initialize g = 0.
     • Loop through multiples of 1, i.e., all numbers from 1 to 12. For each multiple, update g with the GCD value of g and the multiple if it exists in vis.
     • Since everything divides by 1, the GCD will stay 1.
     • We find a subsequence: [3], [6], [12], where the GCD is 1.
   • For x = 2:
     • Initialize g = 0.
     • Loop through multiples of 2: 2, 4, 6, 8, 10, 12.
     • When we reach 6 (which exists in vis), we calculate the GCD of g (which is 0 initially) and 6, resulting in a GCD of 6.
     • Since 6 is not 2, we go on until we reach 12. The GCD of 6 and 12 is still 6. Since we never reached a GCD of 2, 2 is not counted.
   • For x = 3:
     • Initialize g = 0.
     • Loop through multiples of 3: 3, 6, 9, 12. The first multiple we encounter is 3, which exists in vis. The GCD of 0 and 3 is 3.
     • As g = x, we've found a subsequence with this GCD and increment ans by 1.
     • The same will hold true at multiple 6 and 12, we already have g = 3, so we stop checking further multiples.
   • Continue this process for each integer x up to 12.

5. Check Multiples and Calculate GCD: As shown in steps for x = 1, 2, and 3, we calculate the GCD for each multiple within vis, and if at any point g equals x, we count it in our answer and stop checking further multiples of x.

6. Return Result: After iterating over all numbers from 1 to 12, we count all the unique GCDs that we found. In this example, the final count would be the GCDs obtained from all the unique subsequences, which would include 1 (from every possible subsequence), 3 (from [3], [3,6], [3,12], [3,6,12]), and 6 (from [6,12]), giving us a total of 3 distinct GCDs.

In conclusion, the returned value for this nums array would be 3, as there are three different possible GCDs for the non-empty subsequences in the array.

Solution Implementation

Time and Space Complexity

The code defines a function that counts the number of different greatest common divisors (GCDs) of all subsequences of the input array.

Time Complexity:

Let's denote n as the length of the array nums and mx as the maximum value in nums.

First, the function computes the maximum value from nums using max(nums), which takes O(n) time.

Next, the function iterates from 1 to mx with nested loops:

• The outer loop runs mx times.
• The inner loop runs at most mx / x times for each value of x, because it increments by x on each iteration.

Within the inner loop, operations include checking membership in a set vis and computing the GCD, both of which are O(1) operations on average due to hashing for set membership and efficient algorithms for computing GCD (like Euclid's algorithm).

The costly part comes from the nested loops, so the total time complexity is: O(n) + O(mx * ∑(1 .. mx) (1/x)) which simplifies to O(n) + O(mx * ln(mx)) because the harmonic series ∑(1 .. mx) (1/x) roughly approximates the natural logarithm of mx.

Thus, the time complexity of the function is O(n + mx * ln(mx)).

Space Complexity:

The space is spent on:

• Storing vis, which is a set of elements in nums. It therefore requires O(n) space.
• Storing the mx, g, and ans variables, which require O(1) space.

Consequently, the space complexity of the function is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.