Count sequences to k

Array Math Dynamic Programming Memoization Number Theory

35.5% acceptance

Mar 16, 2026

You are given an integer array nums, and an integer k. Start with val = 1. For each nums[i], choose: multiply, divide, or leave unchanged. Division is rational (exact). Count distinct sequences where val == k.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_sequences(nums: Vec<i32>, k: i64) -> i32 {
    // Since nums[i] in 1..=6, the value is always a rational number whose
    // numerator and denominator are products of subsets of {1,2,3,4,5,6}.
    // We can represent val as (numerator, denominator) in reduced form.
    // Use HashMap-based DP.
    use std::collections::HashMap;

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

    // State: (numerator, denominator) in reduced form
    // dp maps state -> count of ways
    let mut dp: HashMap<(i64, i64), i64> = HashMap::new();
    dp.insert((1, 1), 1);

    for &num in &nums {
      let num = num as i64;
      let mut new_dp: HashMap<(i64, i64), i64> = HashMap::new();

      for (&(n, d), &cnt) in &dp {
        // Option 1: leave unchanged
        *new_dp.entry((n, d)).or_insert(0) += cnt;

        // Option 2: multiply by num -> (n * num, d), reduce
        {
          let nn = n * num;
          let nd = d;
          let g = gcd(nn, nd);
          let key = (nn / g, nd / g);
          *new_dp.entry(key).or_insert(0) += cnt;
        }

        // Option 3: divide by num -> (n, d * num), reduce
        {
          let nn = n;
          let nd = d * num;
          let g = gcd(nn, nd);
          let key = (nn / g, nd / g);
          *new_dp.entry(key).or_insert(0) += cnt;
        }
      }

      dp = new_dp;
    }

    // k is integer, so we want state (k, 1)
    *dp.get(&(k, 1)).unwrap_or(&0) as i32
  }
}