LeetCode 1819. Number of Different Subsequences GCDs

Problem

leetcode.com/contest/weekly-contest-235/problems/number-of-different-subsequences-gcds/

Solving

The maximum size of the input is 10^5(n). Elements of input are less than or equal to 2*10^5(m).

My first approache was to apply dynamic programming, but I was not able to figure out a way to divide the proglem into smaller ones.

Brute forth came up in my mind secondly.

The main idea is to iterate over all the possible candidate numbers as GCD, and see if the number is a feasible GCD for a subsequence of the input. So let's say we have a number x. To see if the number x is a feasible GCD for a subsequence of the input, we can calculate GCD of numbers in the input where each of the number is a multiple of x. In other words, we can iterate over all of the multiplications of x, and see if there's a number in the input which is the multiple of x. We can build a set for the existence check which will take O(n). The double loop for iterating all the numbers and multiples of the number is bound to O(m log  m). So the time complexity of the algorithm would be O(m log m log n).

Solution

use std::collections::HashSet;

fn gcd(x: i32, y: i32) -> i32 {
    if y == 0 {
        x
    } else {
        gcd(y, x % y)
    }
}

impl Solution {
    pub fn count_different_subsequence_gc_ds(nums: Vec<i32>) -> i32 {
        let max_val = *nums.iter().max().unwrap();
        let mut s = HashSet::new();
        for x in nums {
            s.insert(x);
        }
        let mut res = 0;
        for x in 1..(max_val + 1) {
            let mut g = -1;
            for d in (x..(max_val + 1)).step_by(x as usize) {
                if s.contains(&d) {
                    if g == -1 {
                        g = d;
                    } else {
                        g = gcd(g, d);
                    }
                }
            }
            if g == x {
                res += 1;
            }
        }
        res
    }
}

Retrospective

1. Had to google for an accruate GCD implementation. Need regular practice.
2. Spent so much time on DP solution. Next time, need to see if there's any chance of converting the givien problem to a desicion problem when the problem is asking for number of feasible cases.