1819. Number of Different Subsequences GCDs LeetCode Solution
In this guide, you will get 1819. Number of Different Subsequences GCDs LeetCode Solution with the best time and space complexity. The solution to Number of Different Subsequences GCDs problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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
Complexity Analysis
Time Complexity: O(n\log n)
Space Complexity: O(n)
1819. Number of Different Subsequences GCDs LeetCode Solution in C++
class Solution {
public:
int countDifferentSubsequenceGCDs(vector<int>& nums) {
const int maxNum = ranges::max(nums);
int ans = 0;
// factor[i] := the GCD of numbers having factor i
vector<int> factor(maxNum + 1);
for (const int num : nums)
for (int i = 1; i * i <= num; ++i)
if (num % i == 0) {
const int j = num / i;
factor[i] = __gcd(factor[i], num);
factor[j] = __gcd(factor[j], num);
}
for (int i = 1; i <= maxNum; ++i)
if (factor[i] == i)
++ans;
return ans;
}
}; /* code provided by PROGIEZ */
1819. Number of Different Subsequences GCDs LeetCode Solution in Java
class Solution {
public int countDifferentSubsequenceGCDs(int[] nums) {
final int maxNum = Arrays.stream(nums).max().getAsInt();
int ans = 0;
// factor[i] := the GCD of numbers having factor i
int[] factor = new int[maxNum + 1];
for (final int num : nums)
for (int i = 1; i * i <= num; ++i)
if (num % i == 0) {
final int j = num / i;
factor[i] = gcd(factor[i], num);
factor[j] = gcd(factor[j], num);
}
for (int i = 1; i <= maxNum; ++i)
if (factor[i] == i)
++ans;
return ans;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
} // code provided by PROGIEZ
1819. Number of Different Subsequences GCDs LeetCode Solution in Python
