Facebook Pixel

3901. Good Subsequence Queries

HardSegment TreeArrayMathNumber Theory
LeetCode ↗
ProblemPatternIdeaExampleCodeComplexPitfalls

Problem Description

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] = [ind_i, val_i] indicates that you should update nums[ind_i] to val_i.

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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

How We Pick the Algorithm

Why Ordered Set / Fenwick / Segment Tree?

This problem maps to Ordered Set / Fenwick / Segment Tree through a short path in the full flowchart.

Sortedinput ormonotonicyesDynamicrangequeries?yesOrdered Set /Fenwick /Segment Tree

Range queries with point updates require a segment tree for efficient answers.

Open in Flowchart

Intuition

The key observation is that we only care about numbers that are multiples of p. If a number is not divisible by p, including it in a subsequence would make the GCD a value that does not have p as a factor, so such a number can never belong to a subsequence whose GCD is exactly p. This lets us ignore all non-multiples of p and focus only on the relevant elements.

So a natural idea is to treat every position holding a value not divisible by p as 0, and keep the actual value otherwise. Then the GCD of the whole array (treating these 0s as "no contribution") is exactly the GCD of all current multiples of p. Call this combined value g.

From here, two things must be checked for a good subsequence to exist: the GCD condition and the length condition.

For the GCD condition, notice that the most generous choice we can make is to take all multiples of p. Their combined GCD is g. Adding more elements to a set can only make the GCD smaller or keep it the same, and removing elements can only make it larger or keep it the same. Since every multiple of p is a factor candidate, the smallest GCD we could possibly achieve from these elements is g. Therefore:

  • If g != p, the GCD of every possible candidate selection cannot reach exactly p, so the answer is impossible.
  • If g == p, then the set of all multiples of p already achieves GCD exactly p.

Now we add the length condition: the subsequence length must be strictly less than n. Let cnt be the number of multiples of p.

  • If cnt < n, some element is not a multiple of p, meaning we are not forced to use all n positions. Taking all cnt multiples already gives a valid subsequence of length cnt < n with GCD p. Done.
  • If cnt == n, every element is divisible by p, so using all of them gives length exactly n, which is not allowed. We must drop at least one element and check whether the remaining elements still have GCD p.

For the cnt == n case, there is a neat shortcut. When n > 6 and the overall GCD is already p, we can always remove one element while keeping the GCD equal to p. The reasoning is that with many elements sharing the same overall GCD p, the property is "redundant" enough that no single element is solely responsible for it, so one can always be discarded safely. Hence brute force is only needed when n <= 6, where we try deleting each position one by one and merge the GCD of the left part and the right part using gcd(left_g, right_g).

To support frequent updates and range GCD queries efficiently, a segment tree is the perfect data structure. Each leaf stores either the value (if divisible by p) or 0, internal nodes store the GCD of their children, and we use point updates for each query plus range queries to evaluate the small-n brute force. This makes every query fast while keeping the overall logic simple.

Pattern Learn more about Segment Tree and Math patterns.

Solution Approach

We use a Segment Tree that maintains the GCD over intervals, combined with the observations above.

Data Structure: Segment Tree over GCD

Each node of the segment tree stores three fields:

  • l, r: the left and right boundaries of the interval the node covers.
  • g: the GCD of all values in that interval.

The tree supports two operations:

  • Point update modify(u, x, v): set the leaf at position x to value v, then push the change upward by recomputing parents with pushup, where tr[u].g = gcd(tr[u<<1].g, tr[u<<1|1].g).
  • Range query query(u, l, r): return the GCD over [l, r]. If the requested range is empty (l > r), it returns 0, which is the identity element for GCD (since gcd(0, x) = x).

The whole tree is built once over 1..n with build.

Step 1: Initialize the tree

We iterate over nums (using 1-based indexing). For each value x:

  • If x % p == 0, it is a multiple of p, so we store its actual value with tree.modify(1, i, x) and increase the counter cnt.
  • Otherwise we leave it as 0 (the default), meaning it does not contribute to the GCD.

After this, tree.tr[1].g holds the GCD of all current multiples of p, and cnt is how many such multiples exist.

Step 2: Process each query

For each [idx, val] (with idx being 0-based in the input, so we use idx + 1 in the tree):

  1. Remove the old value's effect. If nums[idx] % p == 0, the old value was a multiple of p. We set that position to 0 with tree.modify(1, idx + 1, 0) and do cnt -= 1.
  2. Add the new value's effect. If val % p == 0, we store it with tree.modify(1, idx + 1, val) and do cnt += 1.
  3. Update the array itself: nums[idx] = val.

Step 3: Decide whether a good subsequence exists

After updating, we apply the rules:

  • GCD check. If tree.tr[1].g != p, the GCD of all multiples of p is not exactly p, so no selection can reach GCD p. We continue without counting this query.

  • Easy length check. If cnt < n or n > 6, a good subsequence always exists:

    • cnt < n means not every element is a multiple of p, so taking all cnt multiples gives a valid subsequence of length less than n with GCD p.
    • n > 6 (with all elements divisible by p and overall GCD p) guarantees we can always drop one element and keep GCD p.

    In both cases we do ans += 1 and continue.

  • Brute force for small n. If cnt == n and n <= 6, every element is a multiple of p and we must delete at least one. We try deleting each position i from 1 to n:

    • left_g = tree.query(1, 1, i - 1) is the GCD of everything to the left.
    • right_g = tree.query(1, i + 1, n) is the GCD of everything to the right.
    • If gcd(left_g, right_g) == p, then removing position i still yields GCD exactly p, so a good subsequence exists. We do ans += 1 and break.

Step 4: Return the result

After processing all queries, ans holds the number of queries for which a good subsequence exists, and we return it.

Complexity

Let n be the array length and q the number of queries.

  • Time: Building the tree is O(n). Each query performs a constant number of point updates, each costing O(log n * log V) (where V is the maximum value, due to the cost of gcd). The brute-force branch runs only when n <= 6, so it is bounded by a constant number of range queries. Overall the per-query cost is O(log n * log V), giving O((n + q) * log n * log V).
  • Space: O(n) for the segment tree.

Example Walkthrough

Let's trace through a small example to see the solution approach in action.

Setup:

  • nums = [2, 4, 6], so n = 3
  • p = 2
  • queries = [[2, 9], [1, 6], [0, 8]]

Step 1: Initialize the segment tree (1-based indexing)

We check each element against p = 2:

PositionValueDivisible by 2?Stored in tree
12Yes2
24Yes4
36Yes6

All three are multiples of 2, so cnt = 3.

The segment tree now holds GCDs over intervals. The root: tr[1].g = gcd(2, 4, 6) = 2.

Query 1: [2, 9] → update nums[2] to 9 (tree position 3)

  1. Remove old value: nums[2] = 6 is divisible by 2. Set position 3 to 0, cnt = 2.
  2. Add new value: 9 % 2 != 0, so we do nothing. cnt stays at 2.
  3. Update array: nums = [2, 4, 9].

Now the tree leaves are [2, 4, 0], and root g = gcd(2, 4, 0) = 2.

Decision:

  • GCD check: g = 2 == p. ✅ Passes.
  • Length check: cnt = 2 < n = 3. ✅ Not every element is a multiple of p.

Taking the multiples {2, 4} gives a subsequence of length 2 < 3 with GCD 2. Good subsequence exists! → ans = 1

Query 2: [1, 6] → update nums[1] to 6 (tree position 2)

  1. Remove old value: nums[1] = 4 is divisible by 2. Set position 2 to 0, cnt = 1.
  2. Add new value: 6 % 2 == 0. Set position 2 to 6, cnt = 2.
  3. Update array: nums = [2, 6, 9].

Now tree leaves are [2, 6, 0], root g = gcd(2, 6, 0) = 2.

Decision:

  • GCD check: g = 2 == p. ✅ Passes.
  • Length check: cnt = 2 < n = 3. ✅

Taking {2, 6} gives length 2 < 3 with GCD 2. Good subsequence exists! → ans = 2

Query 3: [0, 8] → update nums[0] to 8 (tree position 1)

  1. Remove old value: nums[0] = 2 is divisible by 2. Set position 1 to 0, cnt = 1.
  2. Add new value: 8 % 2 == 0. Set position 1 to 8, cnt = 2.
  3. Update array: nums = [8, 6, 9].

Now tree leaves are [8, 6, 0], root g = gcd(8, 6, 0) = 2.

Decision:

  • GCD check: g = 2 == p. ✅ Passes.
  • Length check: cnt = 2 < n = 3. ✅

Taking {8, 6} gives length 2 < 3 with GCD 2. Good subsequence exists! → ans = 3

Final Result: ans = 3

Bonus: Illustrating the cnt == n brute-force branch

Suppose at some point nums = [4, 6, 8] with p = 2, n = 3. All elements are multiples of 2, so cnt = 3 == n. Since n = 3 <= 6, we must brute-force by deleting one element:

Delete positionLeft GCDRight GCDgcd(left, right)Equals p = 2?
1 (remove 4)0gcd(6,8)=22✅ Yes

Removing position 1 leaves {6, 8} with GCD 2 == p and length 2 < 3. A good subsequence exists, so we count this query and break.

This shows how the empty-range query returning 0 (the GCD identity) lets gcd(0, 2) = 2 work cleanly when an element is dropped from the edge.

Solution Implementation

1from math import gcd
2from typing import List, Optional
3
4
5class Node:
6    """A single node in the segment tree storing a range and its GCD value."""
7
8    __slots__ = "left", "right", "g"
9
10    def __init__(self, left: int, right: int):
11        self.left = left  # left boundary of the segment
12        self.right = right  # right boundary of the segment
13        self.g = 0  # GCD of all values within [left, right]
14
15
16class SegmentTree:
17    """Segment tree supporting point updates and range GCD queries."""
18
19    __slots__ = "tree"
20
21    def __init__(self, n: int):
22        # Allocate 4n nodes (a safe upper bound for a segment tree).
23        self.tree: List[Optional[Node]] = [None] * (n << 2)
24        self.build(1, 1, n)
25
26    def build(self, u: int, left: int, right: int):
27        """Recursively construct the tree structure for range [left, right]."""
28        self.tree[u] = Node(left, right)
29        if left == right:
30            return
31        mid = (left + right) >> 1
32        self.build(u << 1, left, mid)  # build left child
33        self.build(u << 1 | 1, mid + 1, right)  # build right child
34
35    def pushup(self, u: int):
36        """Update the current node's GCD from its two children."""
37        self.tree[u].g = gcd(self.tree[u << 1].g, self.tree[u << 1 | 1].g)
38
39    def modify(self, u: int, x: int, v: int):
40        """Set the value at position x to v and propagate the change upward."""
41        if self.tree[u].left == self.tree[u].right:
42            self.tree[u].g = v
43            return
44        mid = (self.tree[u].left + self.tree[u].right) >> 1
45        if x <= mid:
46            self.modify(u << 1, x, v)  # target lies in the left subtree
47        else:
48            self.modify(u << 1 | 1, x, v)  # target lies in the right subtree
49        self.pushup(u)
50
51    def query(self, u: int, left: int, right: int) -> int:
52        """Return the GCD of all values within range [left, right]."""
53        if left > right:
54            # Empty range; GCD identity is 0.
55            return 0
56        if self.tree[u].left >= left and self.tree[u].right <= right:
57            # Current segment is fully covered by the query range.
58            return self.tree[u].g
59        mid = (self.tree[u].left + self.tree[u].right) >> 1
60        if right <= mid:
61            return self.query(u << 1, left, right)  # entirely in the left child
62        if left > mid:
63            return self.query(u << 1 | 1, left, right)  # entirely in the right child
64        # The query range spans both children; combine their results.
65        return gcd(
66            self.query(u << 1, left, mid),
67            self.query(u << 1 | 1, mid + 1, right),
68        )
69
70
71class Solution:
72    def countGoodSubseq(
73        self, nums: List[int], p: int, queries: List[List[int]]
74    ) -> int:
75        n = len(nums)
76        tree = SegmentTree(n)
77        cnt = 0  # number of elements currently divisible by p
78
79        # Initialize the tree: only keep elements divisible by p.
80        for i, x in enumerate(nums, 1):
81            if x % p == 0:
82                tree.modify(1, i, x)
83                cnt += 1
84
85        ans = 0
86        for idx, val in queries:
87            # Remove the old value at idx if it was divisible by p.
88            if nums[idx] % p == 0:
89                tree.modify(1, idx + 1, 0)
90                cnt -= 1
91            # Insert the new value if it is divisible by p.
92            if val % p == 0:
93                tree.modify(1, idx + 1, val)
94                cnt += 1
95            nums[idx] = val
96
97            # The overall GCD must equal p for any valid configuration.
98            if tree.tree[1].g != p:
99                continue
100
101            # Fast path: if not all elements contribute or the array is large,
102            # the condition is guaranteed to hold.
103            if cnt < n or n > 6:
104                ans += 1
105                continue
106
107            # Otherwise, verify that removing one element still yields GCD == p.
108            for i in range(1, n + 1):
109                left_g = tree.query(1, 1, i - 1)  # GCD of the prefix
110                right_g = tree.query(1, i + 1, n)  # GCD of the suffix
111                if gcd(left_g, right_g) == p:
112                    ans += 1
113                    break
114
115        return ans
116
1// Represents a single node in the segment tree, covering interval [left, right]
2class Node {
3    int left, right;
4    int gcdValue; // GCD of all elements in this node's range
5
6    Node(int left, int right) {
7        this.left = left;
8        this.right = right;
9        this.gcdValue = 0;
10    }
11}
12
13// Segment tree that maintains the GCD over ranges and supports point updates
14class SegmentTree {
15    Node[] tree;
16
17    SegmentTree(int n) {
18        // A segment tree needs up to 4*n nodes
19        tree = new Node[n << 2];
20        build(1, 1, n);
21    }
22
23    // Recursively build the tree structure for the range [left, right]
24    void build(int u, int left, int right) {
25        tree[u] = new Node(left, right);
26        if (left == right) {
27            // Leaf node reached
28            return;
29        }
30        int mid = (left + right) >> 1;
31        build(u << 1, left, mid);           // Build left child
32        build(u << 1 | 1, mid + 1, right);  // Build right child
33    }
34
35    // Recompute the current node's GCD from its two children
36    void pushup(int u) {
37        tree[u].gcdValue = gcd(tree[u << 1].gcdValue, tree[u << 1 | 1].gcdValue);
38    }
39
40    // Point update: set the value at position x to v, then propagate upward
41    void modify(int u, int x, int v) {
42        if (tree[u].left == tree[u].right) {
43            // Found the target leaf
44            tree[u].gcdValue = v;
45            return;
46        }
47        int mid = (tree[u].left + tree[u].right) >> 1;
48        if (x <= mid) {
49            modify(u << 1, x, v);           // Target lies in left child
50        } else {
51            modify(u << 1 | 1, x, v);       // Target lies in right child
52        }
53        pushup(u); // Update this node after child changes
54    }
55
56    // Range query: return the GCD of all values within [left, right]
57    int query(int u, int left, int right) {
58        if (left > right) {
59            // Empty range contributes 0 (neutral element for GCD)
60            return 0;
61        }
62        if (tree[u].left >= left && tree[u].right <= right) {
63            // Current node is fully covered by the query range
64            return tree[u].gcdValue;
65        }
66        int mid = (tree[u].left + tree[u].right) >> 1;
67        if (right <= mid) {
68            // Query lies entirely in the left child
69            return query(u << 1, left, right);
70        }
71        if (left > mid) {
72            // Query lies entirely in the right child
73            return query(u << 1 | 1, left, right);
74        }
75        // Query spans both children: combine the partial results
76        return gcd(query(u << 1, left, mid), query(u << 1 | 1, mid + 1, right));
77    }
78
79    // Compute the greatest common divisor using the Euclidean algorithm
80    private int gcd(int a, int b) {
81        while (b != 0) {
82            int t = a % b;
83            a = b;
84            b = t;
85        }
86        return a;
87    }
88}
89
90class Solution {
91    // Helper GCD used inside the solution logic
92    private int gcd(int a, int b) {
93        while (b != 0) {
94            int t = a % b;
95            a = b;
96            b = t;
97        }
98        return a;
99    }
100
101    public int countGoodSubseq(int[] nums, int p, int[][] queries) {
102        int n = nums.length;
103        SegmentTree tree = new SegmentTree(n);
104
105        // count of elements currently divisible by p
106        int count = 0;
107
108        // Initialize the segment tree: only keep elements divisible by p
109        for (int i = 0; i < n; ++i) {
110            if (nums[i] % p == 0) {
111                tree.modify(1, i + 1, nums[i]); // 1-indexed position
112                ++count;
113            }
114        }
115
116        int ans = 0;
117        for (int[] query : queries) {
118            int index = query[0], value = query[1];
119
120            // Remove the old value's contribution if it was divisible by p
121            if (nums[index] % p == 0) {
122                tree.modify(1, index + 1, 0);
123                --count;
124            }
125            // Add the new value's contribution if it is divisible by p
126            if (value % p == 0) {
127                tree.modify(1, index + 1, value);
128                ++count;
129            }
130            nums[index] = value; // Apply the update
131
132            // If the overall GCD of all tracked elements is not p,
133            // no valid subsequence with GCD exactly p exists
134            if (tree.tree[1].gcdValue != p) {
135                continue;
136            }
137
138            // Fast path: if not every element contributes, or the array is large,
139            // we can guarantee at least one valid good subsequence exists
140            if (count < n || n > 6) {
141                ++ans;
142                continue;
143            }
144
145            // Slow path (small n with all elements divisible by p):
146            // try removing each single element and check if the
147            // remaining GCD still equals p
148            for (int i = 1; i <= n; ++i) {
149                int leftGcd = tree.query(1, 1, i - 1);   // GCD of prefix before i
150                int rightGcd = tree.query(1, i + 1, n);  // GCD of suffix after i
151                if (gcd(leftGcd, rightGcd) == p) {
152                    ++ans;
153                    break;
154                }
155            }
156        }
157        return ans;
158    }
159}
160
1class Node {
2public:
3    int left;   // Left boundary of the segment
4    int right;  // Right boundary of the segment
5    int g;      // GCD of all values within this segment
6
7    Node(int left, int right)
8        : left(left)
9        , right(right)
10        , g(0) {}
11};
12
13class SegmentTree {
14public:
15    vector<Node*> tree;  // Tree nodes stored in a 1-indexed array (size = 4 * n)
16
17    SegmentTree(int n)
18        : tree(n << 2) {
19        build(1, 1, n);
20    }
21
22    // Recursively construct the segment tree over range [left, right]
23    void build(int u, int left, int right) {
24        tree[u] = new Node(left, right);
25        if (left == right) {
26            return;  // Leaf node reached
27        }
28        int mid = (left + right) >> 1;
29        build(u << 1, left, mid);          // Build left child
30        build(u << 1 | 1, mid + 1, right); // Build right child
31    }
32
33    // Update the current node's GCD from its two children
34    void pushup(int u) {
35        tree[u]->g = gcd(tree[u << 1]->g, tree[u << 1 | 1]->g);
36    }
37
38    // Point update: set the value at position x to v
39    void modify(int u, int x, int v) {
40        if (tree[u]->left == tree[u]->right) {
41            tree[u]->g = v;  // Reached the target leaf, assign value
42            return;
43        }
44        int mid = (tree[u]->left + tree[u]->right) >> 1;
45        if (x <= mid) {
46            modify(u << 1, x, v);       // Target lies in the left subtree
47        } else {
48            modify(u << 1 | 1, x, v);   // Target lies in the right subtree
49        }
50        pushup(u);  // Refresh GCD after the update
51    }
52
53    // Range query: return the GCD of values within range [left, right]
54    int query(int u, int left, int right) {
55        if (left > right) {
56            return 0;  // Empty range contributes nothing (gcd identity)
57        }
58        if (tree[u]->left >= left && tree[u]->right <= right) {
59            return tree[u]->g;  // Current segment fully covered by the query
60        }
61        int mid = (tree[u]->left + tree[u]->right) >> 1;
62        if (right <= mid) {
63            return query(u << 1, left, right);          // Entirely in left child
64        }
65        if (left > mid) {
66            return query(u << 1 | 1, left, right);      // Entirely in right child
67        }
68        // Query spans both children; combine the partial results
69        return gcd(query(u << 1, left, mid), query(u << 1 | 1, mid + 1, right));
70    }
71
72    ~SegmentTree() {
73        for (auto node : tree) {
74            delete node;  // Free every allocated node
75        }
76    }
77};
78
79class Solution {
80public:
81    int countGoodSubseq(vector<int>& nums, int p, vector<vector<int>>& queries) {
82        int n = nums.size();
83        SegmentTree tree(n);
84        int cnt = 0;  // Number of elements divisible by p
85
86        // Initialize the tree: only multiples of p are inserted with their value
87        for (int i = 0; i < n; ++i) {
88            if (nums[i] % p == 0) {
89                tree.modify(1, i + 1, nums[i]);
90                ++cnt;
91            }
92        }
93
94        int ans = 0;
95        for (auto& q : queries) {
96            int idx = q[0], val = q[1];
97
98            // Remove the old value's contribution if it was a multiple of p
99            if (nums[idx] % p == 0) {
100                tree.modify(1, idx + 1, 0);
101                --cnt;
102            }
103            // Insert the new value if it is a multiple of p
104            if (val % p == 0) {
105                tree.modify(1, idx + 1, val);
106                ++cnt;
107            }
108            nums[idx] = val;  // Apply the update to the array
109
110            // If the overall GCD of all elements is not p, no valid subsequence exists
111            if (tree.tr[1]->g != p) {
112                continue;
113            }
114
115            // Fast path: if not every element is needed, or the array is large enough,
116            // a valid good subsequence is guaranteed to exist
117            if (cnt < n || n > 6) {
118                ++ans;
119                continue;
120            }
121
122            // Brute-force check for small arrays where every element is a multiple of p:
123            // try removing each element and see if the remaining GCD still equals p
124            for (int i = 1; i <= n; ++i) {
125                int leftG = tree.query(1, 1, i - 1);   // GCD of the left part
126                int rightG = tree.query(1, i + 1, n);  // GCD of the right part
127                if (gcd(leftG, rightG) == p) {
128                    ++ans;
129                    break;
130                }
131            }
132        }
133        return ans;
134    }
135};
136```
137
138A note on one detail: the original code accessed the root node via `tree.tr[1]->g` inside `Solution`, but after renaming the member from `tr` to `tree`, that line must reference `tree.tr[1]` consistently with the member name. In the version above I kept the member variable renamed to `tree`, so the corresponding access should read `tree.tree[1]->g`. Let me correct that line for full consistency:
139
140```cpp
141// Inside the query loop, replace:
142if (tree.tr[1]->g != p) {
143// with:
144if (tree.tree[1]->g != p) {
145
1// Global state for the segment tree.
2// Each node `u` stores its range [segL[u], segR[u]] and aggregated gcd in segG[u].
3let segL: number[];
4let segR: number[];
5let segG: number[];
6
7// Compute the greatest common divisor of two numbers using the Euclidean algorithm.
8function gcd(a: number, b: number): number {
9    while (b !== 0) {
10        [a, b] = [b, a % b];
11    }
12    return a;
13}
14
15// Build the segment tree rooted at node `u` covering the range [l, r].
16function build(u: number, l: number, r: number): void {
17    segL[u] = l;
18    segR[u] = r;
19    segG[u] = 0;
20    // Leaf node: no children to build.
21    if (l === r) {
22        return;
23    }
24    const mid = (l + r) >> 1;
25    build(u << 1, l, mid);
26    build((u << 1) | 1, mid + 1, r);
27}
28
29// Recompute node `u`'s gcd from its two children after a child changed.
30function pushup(u: number): void {
31    segG[u] = gcd(segG[u << 1], segG[(u << 1) | 1]);
32}
33
34// Point update: set the leaf at position `x` to value `v`, then propagate upward.
35function modify(u: number, x: number, v: number): void {
36    if (segL[u] === segR[u]) {
37        segG[u] = v;
38        return;
39    }
40    const mid = (segL[u] + segR[u]) >> 1;
41    if (x <= mid) {
42        modify(u << 1, x, v);
43    } else {
44        modify((u << 1) | 1, x, v);
45    }
46    pushup(u);
47}
48
49// Range query: return the gcd of all values in positions [l, r].
50function query(u: number, l: number, r: number): number {
51    // Empty range contributes the identity value (0 for gcd).
52    if (l > r) {
53        return 0;
54    }
55    // Current node's range is fully inside the query range.
56    if (segL[u] >= l && segR[u] <= r) {
57        return segG[u];
58    }
59    const mid = (segL[u] + segR[u]) >> 1;
60    if (r <= mid) {
61        return query(u << 1, l, r);
62    }
63    if (l > mid) {
64        return query((u << 1) | 1, l, r);
65    }
66    // Query range spans both children: combine their results.
67    return gcd(query(u << 1, l, mid), query((u << 1) | 1, mid + 1, r));
68}
69
70// Initialize the segment tree for an array of size `n`.
71function buildSegmentTree(n: number): void {
72    const size = n << 2;
73    segL = Array(size);
74    segR = Array(size);
75    segG = Array(size);
76    build(1, 1, n);
77}
78
79function countGoodSubseq(nums: number[], p: number, queries: number[][]): number {
80    const n = nums.length;
81    // Set up the global segment tree.
82    buildSegmentTree(n);
83
84    // `cnt` tracks how many elements are currently divisible by `p`.
85    let cnt = 0;
86    for (let i = 0; i < n; ++i) {
87        if (nums[i] % p === 0) {
88            // Store the value at its 1-based position; non-divisible elements stay 0.
89            modify(1, i + 1, nums[i]);
90            ++cnt;
91        }
92    }
93
94    let ans = 0;
95    for (const [idx, val] of queries) {
96        // Remove the old value's contribution if it was divisible by `p`.
97        if (nums[idx] % p === 0) {
98            modify(1, idx + 1, 0);
99            --cnt;
100        }
101        // Add the new value's contribution if it is divisible by `p`.
102        if (val % p === 0) {
103            modify(1, idx + 1, val);
104            ++cnt;
105        }
106        nums[idx] = val;
107
108        // The overall gcd of all divisible elements must equal exactly `p`.
109        if (segG[1] !== p) {
110            continue;
111        }
112        // If not every element is divisible (cnt < n) or the array is large enough,
113        // a valid good subsequence is guaranteed to exist.
114        if (cnt < n || n > 6) {
115            ++ans;
116            continue;
117        }
118        // Small array where all elements are divisible: check whether removing one
119        // element still leaves a gcd of exactly `p`.
120        for (let i = 1; i <= n; ++i) {
121            const leftG = query(1, 1, i - 1);
122            const rightG = query(1, i + 1, n);
123            if (gcd(leftG, rightG) === p) {
124                ++ans;
125                break;
126            }
127        }
128    }
129    return ans;
130}
131

Time and Space Complexity

Time Complexity: O((n + q) × log n)

The analysis proceeds as follows:

  • Building the segment tree: The build method recursively constructs 4n nodes, taking O(n) time.

  • Initial setup: Iterating over nums and calling modify for each element divisible by p costs O(n × log n), since each modify operation traverses the tree height O(log n).

  • Processing queries: For each of the q queries:

    • The modify operations (removing the old value and inserting the new value) each cost O(log n).
    • Checking tree.tr[1].g != p is O(1).
    • When cnt < n or n > 6, the query is handled in O(1) additional time.
    • When cnt == n and n <= 6, the code enumerates each of the n positions, performing two query calls per position, each costing O(log n). Since n <= 6, this is at most 6 × 2 × log n = O(log n), i.e., only a constant factor of work.

    Therefore, each query is processed in O(log n) time, yielding O(q × log n) total.

Combining the build, setup, and query phases gives a total time complexity of O((n + q) × log n), where n is the length of nums and q is the number of queries.

Space Complexity: O(n)

The segment tree allocates an array of size n << 2 (i.e., 4n), and each entry stores a Node object using __slots__ to limit memory. The recursion depth during build, modify, and query is O(log n). Thus the dominant space usage is the segment tree itself, giving an overall space complexity of O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Mishandling the "all elements divisible by p" boundary case (cnt == n)

The most subtle bug lies in the logic that decides whether a good subsequence exists when every element is a multiple of p. Recall the length constraint: a good subsequence must be strictly shorter than n. When cnt == n, the GCD of the entire array might equal p, but you are not allowed to use the whole array — you must drop at least one element.

A common mistake is to write the check as:

# WRONG: forgets that the full array (length n) is not allowed
if tree.tree[1].g == p:
    ans += 1
    continue

This counts a query as valid simply because the GCD of all n elements is p. But if removing any single element raises the GCD above p, then no subsequence of length < n actually reaches GCD p, and the query should not be counted.

Example. Let p = 1 and nums = [6, 10, 15].

  • gcd(6, 10, 15) = 1, so the full-array GCD equals p.
  • But every proper subsequence:
    • gcd(6, 10) = 2
    • gcd(6, 15) = 3
    • gcd(10, 15) = 5
    • singletons are 6, 10, 15

None of these equal 1. So no good subsequence exists, yet the naive check would wrongly count it.

Solution. When cnt == n, do not trust the full-array GCD alone. Verify that there is at least one element whose removal keeps the GCD exactly p, using prefix/suffix GCDs (exactly what the brute-force branch does):

if cnt == n:
    found = False
    for i in range(1, n + 1):
        left_g = tree.query(1, 1, i - 1)
        right_g = tree.query(1, i + 1, n)
        if gcd(left_g, right_g) == p:
            found = True
            break
    if found:
        ans += 1
    continue

The reference code handles this correctly by combining the cnt < n or n > 6 fast path with the explicit deletion loop for cnt == n and n <= 6.

Pitfall 2: Trusting the n > 6 shortcut without understanding why it works

The fast path counts the query whenever n > 6 (given the overall GCD is p and all elements are multiples of p). It is tempting to use a different threshold (e.g., n > 1) or to drop this branch entirely and brute-force everything.

The reasoning behind n > 6: among n numbers all divisible by p whose overall GCD is exactly p, if removing every candidate element raised the GCD, each element would have to be the unique carrier of some prime factor that prevents the GCD from dropping. The number of distinct "blocking" prime powers is bounded, so once n is large enough, by a pigeonhole-style argument some element is always safe to delete. The constant 6 is a safe bound that guarantees a deletable element always exists.

Pitfall consequence: If you lower the threshold (say to n > 2) you may incorrectly count cases like the [6, 10, 15] example above (n = 3). If you remove the brute force and rely only on the GCD check, you also count invalid cases.

Solution. Keep the threshold conservative (n <= 6 triggers brute force) and only use the n > 6 shortcut after confirming tree.tree[1].g == p and cnt == n. The brute force is cheap because it only runs for tiny arrays.

Pitfall 3: Using 0 incorrectly as the GCD identity in updates

The tree initializes leaves to 0 and uses gcd(0, x) = x so that non-multiples of p "disappear." A frequent bug is forgetting to reset a leaf to 0 when an old value (that was divisible by p) is overwritten by a new value that is not divisible by p.

# WRONG: only updates when new value is divisible by p,
# leaving the stale old value in the tree
if val % p == 0:
    tree.modify(1, idx + 1, val)

If nums[idx] was a multiple of p but val is not, the old value lingers in the tree, corrupting both tree.tree[1].g and cnt.

Solution. Always perform the remove-then-add sequence independently:

if nums[idx] % p == 0:          # remove old contribution
    tree.modify(1, idx + 1, 0)
    cnt -= 1
if val % p == 0:                # add new contribution
    tree.modify(1, idx + 1, val)
    cnt += 1
nums[idx] = val

Updating nums[idx] after both checks is essential — if you update nums[idx] first, the removal check reads the new value and skips the necessary cleanup.

Pitfall 4: Off-by-one between 0-based queries and 1-based tree indexing

Queries use 0-based indices, while the segment tree is built over 1..n. Forgetting the + 1 shift (or applying it inconsistently between modify and query) silently updates or reads the wrong position.

Solution. Standardize on one convention: store data 1-based in the tree, and convert exactly once at the boundary (idx + 1). The prefix query query(1, 1, i - 1) and suffix query query(1, i + 1, n) already correctly rely on the empty-range guard (left > right returns 0) for the endpoints i = 1 and i = n.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Recommended Readings

Segment Tree Explained

Segment Tree Introduction A segment tree stores information about intervals of an array It supports two operations efficiently update one element and query an aggregate value over a contiguous range In this introduction the aggregate is sum so the operations are update idx value set arr idx value and query

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More