LeetCode 1819. Number of Different Subsequences GCDs Solution in Java, C++, Python & Go | Explanation + Code

Description

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

Solutions

Solution 1: Enumeration + Mathematics

For all sub-sequences of the array nums, their greatest common divisor (GCD) will not exceed the maximum value mx in the array.

Therefore, we can enumerate each number x in [1,.. mx], and determine whether x is the GCD of a sub-sequence of the array nums. If it is, then we increment the answer by one.

So the problem is transformed into: determining whether x is the GCD of a sub-sequence of the array nums. We can do this by enumerating the multiples y of x, and checking whether y exists in the array nums. If y exists in the array nums, then we calculate the GCD g of y. If g = x occurs, then x is the GCD of a sub-sequence of the array nums.

The time complexity is O(n + M × log M), and the space complexity is O(M). Here, n and M are the length of the array nums and the maximum value in the array nums, respectively.

PythonJavaC++Go

class Solution: def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int: mx = max(nums) vis = set(nums) ans = 0 for x in range(1, mx + 1): g = 0 for y in range(x, mx + 1, x): if y in vis: g = gcd(g, y) if g == x: ans += 1 break return ans(code-box)

class Solution { public int countDifferentSubsequenceGCDs(int[] nums) { int mx = Arrays.stream(nums).max().getAsInt(); boolean[] vis = new boolean[mx + 1]; for (int x : nums) { vis[x] = true; } int ans = 0; for (int x = 1; x <= mx; ++x) { int g = 0; for (int y = x; y <= mx; y += x) { if (vis[y]) { g = gcd(g, y); if (x == g) { ++ans; break; } } } } return ans; } private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } }(code-box)

class Solution { public: int countDifferentSubsequenceGCDs(vector<int>& nums) { int mx = *max_element(nums.begin(), nums.end()); vector<bool> vis(mx + 1); for (int& x : nums) { vis[x] = true; } int ans = 0; for (int x = 1; x <= mx; ++x) { int g = 0; for (int y = x; y <= mx; y += x) { if (vis[y]) { g = gcd(g, y); if (g == x) { ++ans; break; } } } } return ans; } };(code-box)

func countDifferentSubsequenceGCDs(nums []int) (ans int) { mx := slices.Max(nums) vis := make([]bool, mx+1) for _, x := range nums { vis[x] = true } for x := 1; x <= mx; x++ { g := 0 for y := x; y <= mx; y += x { if vis[y] { g = gcd(g, y) if g == x { ans++ break } } } } return } func gcd(a, b int) int { if b == 0 { return a } return gcd(b, a%b) }(code-box)