LeetCode 1819: Number of Different Subsequences GCDs

Explanation:

To solve this problem, we need to find the number of different GCDs among all non-empty subsequences of the given array nums. We can approach this problem by iterating through each possible GCD value from 1 to the maximum value in nums and check if that GCD can be formed by any subsequence of nums. We can use the concept of the greatest common divisor (GCD) to find the GCD of subsequences efficiently.

1. Initialize a set to store all possible GCD values.
2. Iterate through all numbers in nums and add them to the set.
3. For each number in nums, iterate through all possible GCD values from 1 to the maximum number in nums.
4. Check if the GCD of the current number and the current possible GCD is in the set, if so, add it to the set.
5. Repeat step 4 for all numbers in nums.
6. Finally, return the size of the set as the result.

Time Complexity: O(n * sqrt(max(nums))) where n is the length of nums and max(nums) is the maximum value in nums. Space Complexity: O(sqrt(max(nums))) for storing the set of GCD values.

class Solution {
    public int countDifferentSubsequenceGCDs(int[] nums) {
        Set<Integer> gcds = new HashSet<>();
        int maxNum = Arrays.stream(nums).max().getAsInt();

        for (int num : nums) {
            gcds.add(num);
        }

        for (int num : nums) {
            for (int i = 1; i <= maxNum; i++) {
                if (gcds.contains(i)) {
                    gcds.add(gcd(num, i));
                }
            }
        }

        return gcds.size();
    }

    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}