Is Good Subsequence Queries easy or hard?

Good Subsequence Queries is considered a Hard problem because it combines multiple advanced ideas. You need to recognize the subsequence DP pattern, optimize repeated transitions, and integrate a logarithmic data structure like a Fenwick tree or segment tree to handle queries efficiently.

Good Subsequence Queries Python/Java solution

Python, Java, and C++ implementations usually follow the same structure: coordinate compression if needed, a Fenwick tree or segment tree for range queries, and DP transitions that update subsequence counts. The complexity remains O((n + q) log n) regardless of language.

What is the best approach for Good Subsequence Queries?

The most efficient solution uses dynamic programming combined with a Fenwick Tree or Segment Tree. The DP tracks how many valid subsequences end at each position, while the tree structure allows fast prefix or range queries. This reduces repeated scans of previous elements and achieves roughly O((n + q) log n) time.

Is Good Subsequence Queries asked at Google/Amazon/Meta?

Subsequence counting with range queries appears frequently in interviews at companies like Google, Amazon, and Meta. The exact problem may vary, but the pattern of combining dynamic programming with a Fenwick tree or segment tree is a common interview technique.

What data structure is used in Good Subsequence Queries?

Efficient solutions rely on Fenwick Trees (Binary Indexed Trees) or Segment Trees. These structures support fast prefix sums or range aggregation, which allows dynamic programming states to be updated and queried in logarithmic time.

What is the time complexity of Good Subsequence Queries?

The optimal implementation runs in O((n + q) log n) time, where n is the array size and q is the number of queries. Each element update and query operation performs logarithmic work in a Fenwick tree or segment tree. Space complexity is typically O(n).

How to solve Good Subsequence Queries in O((n + q) log n)?

Maintain DP counts for subsequences ending at each index and store aggregated values in a Fenwick tree or segment tree. For every element, query the tree to determine how many previous subsequences can extend to form a new valid subsequence. Update the structure with the new count and answer queries using range or prefix sums.

3901. Good Subsequence Queries - Practice Online

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.

Example 1:

Input: nums = [4,8,12,16], p = 2, queries = [[0,3],[2,6]]

Output: 1

Explanation:

i	`[ind_i, val_i]`	Operation	Updated `nums`	Any good Subsequence
0	`[0, 3]`	Update `nums[0]` to `3`	`[3, 8, 12, 16]`	No, as no subsequence has GCD exactly `p = 2`
1	`[2, 6]`	Update `nums[2]` to `6`	`[3, 8, 6, 16]`	Yes, subsequence `[8, 6]` has GCD exactly `p = 2`

Thus, the answer is 1.

Example 2:

Input: nums = [4,5,7,8], p = 3, queries = [[0,6],[1,9],[2,3]]

Output: 2

Explanation:

i	`[ind_i, val_i]`	Operation	Updated `nums`	Any good Subsequence
0	`[0, 6]`	Update `nums[0]` to `6`	`[6, 5, 7, 8]`	No, as no subsequence has GCD exactly `p = 3`
1	`[1, 9]`	Update `nums[1]` to `9`	`[6, 9, 7, 8]`	Yes, subsequence `[6, 9]` has GCD exactly `p = 3`
2	`[2, 3]`	Update `nums[2]` to `3`	`[6, 9, 3, 8]`	Yes, subsequence `[6, 9, 3]` has GCD exactly `p = 3`

Thus, the answer is 2.

Example 3:

Input: nums = [5,7,9], p = 2, queries = [[1,4],[2,8]]

Output: 0

Explanation:

i	`[ind_i, val_i]`	Operation	Updated `nums`	Any good Subsequence
0	`[1, 4]`	Update `nums[1]` to `4`	`[5, 4, 9]`	No, as no subsequence has GCD exactly `p = 2`
1	`[2, 8]`	Update `nums[2]` to `8`	`[5, 4, 8]`	No, as no subsequence has GCD exactly `p = 2`

Thus, the answer is 0.

Constraints:

2 <= n == nums.length <= 5 * 10⁴
1 <= nums[i] <= 5 * 10⁴
1 <= queries.length <= 5 * 10⁴
queries[i] = [ind_i, val_i]
1 <= val_i, p <= 5 * 10⁴
0 <= ind_i <= n - 1