Count Updates That Admit a Proper Subsequence with a Target GCD
Company: Infosys
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
# Count Updates That Admit a Proper Subsequence with a Target GCD
You are given an integer array `nums` of length `n`, a positive integer `p`, and an ordered list of updates `queries`.
A good subsequence is a nonempty subsequence of the current array that:
- contains strictly fewer than `n` elements; and
- has greatest common divisor exactly equal to `p`.
Each update `[index, value]` replaces `nums[index]` with `value`. Apply the updates in their given order, keeping each change for subsequent updates. After every update, decide whether at least one good subsequence exists.
Return the number of updates whose resulting array has a good subsequence. Do not count the initial array before the first update.
### Function
`int countGoodSubseq(vector<int>& nums, int p, vector<vector<int>>& queries)`
### Example 1
**Input:** `nums = [6, 10, 15], p = 1, queries = [[0, 30], [1, 14], [2, 7]]`
**Output:** `2`
**Explanation:**
- After the first update, the array is `[30, 10, 15]`. All its elements are divisible by `5`, so there is no good subsequence for `p = 1`.
- After the second update, `[14, 15]` is a good subsequence of `[30, 14, 15]`.
- After the third update, `[30, 7]` is a good subsequence of `[30, 14, 7]`.
Exactly two resulting arrays qualify.
### Example 2
**Input:** `nums = [6, 10], p = 2, queries = [[0, 6], [1, 2], [1, 2], [1, 10]]`
**Output:** `2`
**Explanation:** Since `n = 2`, a good subsequence must be a singleton.
| Query index | Current array | Good subsequence exists? |
| --- | --- | --- |
| `0` | `[6, 10]` | No: neither singleton has GCD `2`. |
| `1` | `[6, 2]` | Yes: choose `[2]`. |
| `2` | `[6, 2]` | Yes: this update is counted again. |
| `3` | `[6, 10]` | No. |
### Constraints
- `2 <= n == nums.length <= 50000`
- `1 <= nums[i] <= 50000`
- `1 <= queries.length <= 50000`
- Every query contains exactly two integers `[index, value]`.
- `0 <= index < n`
- `1 <= value <= 50000`
- `1 <= p <= 50000`
### Clarifications
- A subsequence may omit arbitrary positions but keeps the order of the chosen positions; it need not be contiguous.
- Choosing the entire array is forbidden, even if its GCD equals `p`.
- Equal values and repeated assignments are allowed. Each query is counted separately.
- All updates belong to this one function call; there is no separate persistent object interface.
### What a Strong Answer Covers
- Enforcing a nonempty, proper subsequence and an exact GCD.
- Applying every update before checking the resulting array.
- Handling repeated indices and the full update count efficiently.
Overview: Process ordered point updates and count the resulting arrays that admit a nonempty proper subsequence whose greatest common divisor equals the target.