Skip to main content
Back to problems
#1819
Hard Algorithms

Number of different subsequences gcds

Array Math Counting Number Theory
45.0% acceptance
Feb 25, 2026
435
48
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. A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array. Return the number of different GCDs among all non-empty subsequences of nums.

Solution

Rust
Time O(n²)
Space O(n)
LeetCode
solution.rs 
impl Solution {
  pub fn count_different_subsequence_gc_ds(nums: Vec<i32>) -> i32 {
    let max_val = *nums.iter().max().unwrap() as usize;
    let mut present = vec![false; max_val + 1];
    for &n in &nums {
      present[n as usize] = true;
    }

    fn gcd(a: usize, b: usize) -> usize {
      if b == 0 { a } else { gcd(b, a % b) }
    }

    let mut count = 0;
    for g in 1..=max_val {
      let mut cur_gcd = 0usize;
      let mut mult = g;
      while mult <= max_val {
        if present[mult] {
          cur_gcd = gcd(cur_gcd, mult);
          if cur_gcd == g {
            count += 1;
            break;
          }
        }
        mult += g;
      }
    }
    count
  }
}