Skip to main content
Talentd

Good Subsequence Queries - Solution & Explanation

HardArrayMathSegment TreeNumber Theory15 min readAsked at: Amazon, Infosys
Practice this problem

Problem Statement

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.

 

Example 1:

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

Output: 1

Explanation:

i [indi, vali] 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 [indi, vali] 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 [indi, vali] 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 * 104
  • 1 <= nums[i] <= 5 * 104
  • 1 <= queries.length <= 5 * 104
  • queries[i] = [indi, vali]
  • 1 <= vali, p <= 5 * 104
  • 0 <= indi <= n - 1

Approach Overview

Problem Overview: You are given an array and multiple queries. Each query asks about the number of good subsequences that satisfy a specific constraint defined in the problem. The challenge is answering many queries efficiently without recomputing subsequences from scratch every time.

Approach 1: Brute Force Enumeration (O(2^n) time, O(n) space)

The most direct idea is to generate every possible subsequence of the array and check whether it satisfies the “good” condition. For each query, filter subsequences that fall within the required constraints and count them. This approach uses recursive generation or bitmask enumeration. The problem is exponential growth: an array of size n has 2^n subsequences, so even moderate inputs become impossible to handle.

Approach 2: Dynamic Programming per Query (O(n^2) time, O(n) space)

A better strategy uses dynamic programming to build subsequences incrementally. Let dp[i] represent the number of valid subsequences ending at index i. For each position, iterate over previous indices and extend subsequences that still satisfy the “good” constraint. For every query, recompute or partially recompute these values within the relevant range. This reduces exponential complexity but still becomes slow when both n and the number of queries are large.

Approach 3: DP with Fenwick Tree / Segment Tree (O((n + q) log n) time, O(n) space)

The optimal solution combines dynamic programming with a range data structure such as a segment tree or Fenwick tree. Instead of scanning all previous elements, the structure maintains aggregated counts of valid subsequences. After coordinate compression (if values are large), each step performs fast prefix or range queries to compute how many subsequences can extend to the current element. Updates insert the new counts back into the tree. Queries can then be answered in logarithmic time using the maintained prefix sums or range aggregates.

This method avoids recomputing subsequences repeatedly. Each element contributes once, and each query performs only logarithmic operations. The combination of DP state transitions and tree-based range queries is a common technique for subsequence counting problems where constraints depend on relative ordering or value ranges.

Recommended for interviews: Interviewers expect the optimized DP with a Fenwick tree or segment tree. Showing the brute-force idea demonstrates understanding of subsequence generation, but recognizing that repeated scans are too slow and replacing them with logarithmic range queries shows strong algorithmic skill.

Solution

We only care about numbers that are multiples of p, because if a number is not divisible by p, it can never belong to a subsequence whose GCD is exactly p.

Therefore, we can treat positions whose values are not divisible by p as 0, and only maintain the following value for each position in the segment tree:

  • If nums[i] is divisible by p, store its actual value in the segment tree.
  • Otherwise, store 0.

In this way, the whole segment tree maintains the GCD of all current multiples of p. Denote it by g:

  • If g \ne p, then no matter how we choose, the GCD of all candidate elements cannot be exactly p, so the answer is definitely false.
  • If g = p, then all multiples of p together already have GCD equal to p.

Next, we still need the subsequence length to be strictly smaller than n.

  • If not all elements are divisible by p, that is, the number of valid elements satisfies cnt < n, then we can directly take all multiples of p, and this is already a good subsequence of length less than n.
  • If cnt = n, then every element is divisible by p, so we must delete at least one element and check whether the GCD of the remaining elements is still p.

Here we use the following fact: if n > 6, all elements are divisible by p, and the overall GCD is already p, then we can always delete one element and still keep the GCD equal to p. So we only need to brute-force the deleted position when n \le 6 and all elements are divisible by p. In that case, we query the GCD of the left part and the right part with the segment tree, and then merge them.

The segment tree supports two operations:

  • Point update: change one position to the new value or to 0.
  • Range query: get the GCD of a given interval.

After each query update, we just apply the rules above to determine whether a good subsequence exists.

The time complexity is O((n + q) times log n). In the worst case, when n \le 6, we additionally enumerate the deleted position for each query, but that is only a constant factor. So the total complexity remains O((n + q) times log n). The space complexity is O(n), where n is the length of nums and q is the number of queries.

Code

PythonC++GoTypeScript

Python

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subsequence EnumerationO(2^n)O(n)Conceptual understanding of subsequences or very small arrays
Dynamic Programming per QueryO(n^2)O(n)When constraints are moderate and query count is small
DP with Fenwick Tree / Segment TreeO((n + q) log n)O(n)Optimal solution for large arrays and many queries

Video Solution

weekly contest 497 | leetcode 3898 | leetcode 3899 | leetcode 3900 | leetcode 3901 | DSA • Code With Vick • 1,243 views views

Watch 2 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Good Subsequence Queries with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays