Problem statement

https://leetcode.com/problems/number-of-different-subsequences-gcds/

Solution

Solution 1

I really hate what it happens that on other languages solution will pass, but not on python.

The idea is the following:

  1. For each num in nums evaluate the list of divisors. Unfortunatelly it is not enough to do it in stupid way, python will not allow this, so I used the idea if we already calculated list of divisors, no need to do it again.

  2. Create defaultdict d, where for each i we correspond it to the list of num from nums, which are divisible by i.

  3. Iterate over d and for each i check if gcd of all numbers in d[i] is equal to i. If it is the case, then number i is gcd of some group of numbers.

Complexity

Time complexity is potentially O(n^1.5), because we iterate to the n^0.5 when we find divisors. However with more detailed analysis it is more like O(m log m), check solution 2. Space complexity is the same.

Code

I think I was lucky that it finally was accepted on contest, now it will give me 9500+ and sometimes TLE

class Solution:
    def countDifferentSubsequenceGCDs(self, nums):
        @lru_cache(None)
        def divisors(n):
            for i in range(2, int(sqrt(n)) + 1):
                if n%i == 0:
                    s = divisors(n//i)
                    return tuple(set(s + tuple(q*i for q in s)))

            return tuple([1, n])
        
        nums = set(nums)
        q = defaultdict(list)
        for num in nums:
            for div in divisors(num):
                q[div].append(num)
                
        ans = 0
        for num in q:
            list_div = q[num]
            s = list_div[0]
            for i in range(1, len(list_div)):
                s = gcd(s, list_div[i])
                if s == num:
                    break

            if s== num: ans += 1
        
        return ans

Solution 2:

The following solution has very similar idea, but smart way to evaluate all divisors. Idea behind is exaclty the same as previously: for each i we check all numbers divisible by i and find if gcd of all those numbers equal to i.

Complexity:

Let m be the biggest number in nums, then there will be no more than m + m/2 + m/3 + ... = O(m log m) divisors in total. So, time complexity can be expressed as O(m*log m). Notice also that it is under assumption that gcd can be evaluated in O(1), which is not exactly the case, it is more like log m, so we need to multiply it by log m factor. Space complexity is the same.

class Solution:
    def countDifferentSubsequenceGCDs(self, nums):
        T = max(nums) + 1
        nums = set(nums)
        ans = 0
            
        for x in range(1, T):
            g = 0
            for y in range(x, T, x):
                if y in nums:
                    g = gcd(g, y)
                if g == x:
                    break
                    
            if g == x: ans += 1
                
        return ans

It also can be written in very short form:

T, nums, ans = max(nums) + 1, set(nums), 0
return sum(gcd(*[y for y in range(x, T, x) if y in nums]) == x for x in range(1, T))

If you like the solution, you can upvote it on leetcode discussion section: Problem 1819