hardArrayCountingMathNumber Theory 0 views
Number of Different Subsequences GCDs
You are given an array nums that consists of positive integers.
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.
A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.
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 <= 10^5
- 1 <= nums[i] <= 2 * 10^5
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.