Good subsequence queries

19.5% acceptance

May 14, 2026

You are given an integer array nums of length n and an integer p. A non-empty subsequence of nums is called good if: Its length is strictly less than n. The greatest common divisor (GCD) of its elements is exactly p. You are also given a 2D integer array queries of length q, where each queries[i] = [indi, vali] indicates that you should update nums[indi] to vali. After each query, determine whether there exists any good subsequence in the current array. Return the number of queries for which a good subsequence exists. The term gcd(a, b) denotes the greatest common divisor of a and b.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_good_subseq(nums: Vec<i32>, p: i32, queries: Vec<Vec<i32>>) -> i32 {
    fn gcd(a: i32, b: i32) -> i32 {
      let (mut a, mut b) = (a, b);
      while b != 0 { let t = a % b; a = b; b = t; }
      a
    }
    let n = nums.len();
    let size = n.next_power_of_two().max(1);
    let mut tree = vec![0i32; 2 * size];
    let mut current = nums.clone();
    let mut cnt_p = 0i32;
    let mut cnt_eq_p = 0i32;
    let set_leaf = |tree: &mut Vec<i32>, size: usize, pos: usize, val: i32| {
      let mut i = pos + size;
      tree[i] = val;
      i /= 2;
      while i > 0 {
        tree[i] = gcd(tree[2 * i], tree[2 * i + 1]);
        i /= 2;
      }
    };
    let query = |tree: &Vec<i32>, size: usize, ql: usize, qr_inclusive: usize| -> i32 {
      if ql > qr_inclusive { return 0; }
      let mut l = ql + size;
      let mut r = qr_inclusive + size + 1;
      let mut res = 0i32;
      while l < r {
        if l & 1 == 1 { res = gcd(res, tree[l]); l += 1; }
        if r & 1 == 1 { r -= 1; res = gcd(res, tree[r]); }
        l /= 2;
        r /= 2;
      }
      res
    };
    for i in 0..n {
      let v = current[i];
      if v % p == 0 {
        cnt_p += 1;
        if v == p { cnt_eq_p += 1; }
        set_leaf(&mut tree, size, i, v / p);
      }
    }
    let mut ans = 0i32;
    for q in &queries {
      let idx = q[0] as usize;
      let val = q[1];
      let old = current[idx];
      if old % p == 0 {
        cnt_p -= 1;
        if old == p { cnt_eq_p -= 1; }
      }
      if val % p == 0 {
        cnt_p += 1;
        if val == p { cnt_eq_p += 1; }
        set_leaf(&mut tree, size, idx, val / p);
      } else {
        set_leaf(&mut tree, size, idx, 0);
      }
      current[idx] = val;
      if cnt_p == 0 { continue; }
      let g = query(&tree, size, 0, n - 1);
      if g != 1 { continue; }
      if (cnt_p as usize) < n {
        ans += 1;
        continue;
      }
      if cnt_eq_p >= 1 {
        ans += 1;
        continue;
      }
      if n >= 8 {
        ans += 1;
        continue;
      }
      let mut found = false;
      for x in 0..n {
        let left = if x == 0 { 0 } else { query(&tree, size, 0, x - 1) };
        let right = if x + 1 >= n { 0 } else { query(&tree, size, x + 1, n - 1) };
        if gcd(left, right) == 1 {
          found = true;
          break;
        }
      }
      if found { ans += 1; }
    }
    ans
  }
}