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.
[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.
[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 <= 1051 <= nums[i] <= 2 * 105When 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:
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:
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)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:
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| Case | How to Handle |
|---|---|
| The list holds a single number | Return one, because the only non-empty group contributes that number itself. |
| Every value is identical | 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 | Count both the shared divisors of the smaller groups and each number on its own. |
| One stored value divides another | Count the smaller value when the multiples of it fold back to that same value. |
| The largest value is one | Return one, because every non-empty group has divisor one. |