Good Subsequence Queries

Problem summary

We are given:

• an array nums
• an integer p
• update queries of the form [index, value]

After every update, we need to check whether the current array contains a good subsequence:

• non-empty
• length strictly smaller than n
• GCD of all chosen elements is exactly p

The final answer is the number of queries for which such a subsequence exists.

First reduction

The only elements that can ever belong to a valid subsequence are the ones divisible by p.

If a number is not divisible by p, it can never appear inside a subsequence whose GCD is exactly p.

So for each value:

• if nums[i] % p != 0, treat it as unusable
• if nums[i] % p == 0, divide it by p

Now the question becomes:

Does there exist a non-empty subsequence of the reduced usable values, with length < n, whose GCD is exactly 1?

That turns the original problem into a dynamic GCD maintenance problem.

Key observation

Let the transformed value at index i be:

nums[i] / p   if nums[i] % p == 0
0             otherwise

Then:

• 0 means this index cannot participate
• positive values are the real candidates
• GCD over the usable elements being 1 is exactly what we want

So we maintain:

1. cnt = how many elements are divisible by p
2. a segment tree storing GCDs of transformed values

The root of the tree tells us the GCD of all usable elements.

When is the answer immediately yes?

There are two easy checks:

1. No usable element exists

If cnt == 0, the answer is obviously false.

2. Some element is unusable

If cnt < n and the GCD of all usable elements is 1, then we can simply take all usable elements.

Why is this valid?

• their GCD is 1 in reduced form, so the original GCD is p
• because at least one array element is unusable, this subsequence is automatically shorter than n

So in this case the answer is immediately true.

The only tricky case

The hard part is when every element is divisible by p, so cnt == n.

Now taking all usable elements means taking the whole array, which is not allowed because a good subsequence must have length strictly less than n.

So we need to know:

Is there some proper subsequence whose reduced GCD is 1?

Here is the nice simplification:

• if any proper subsequence has GCD 1
• then adding more elements keeps the GCD at 1

That means it is enough to check whether removing exactly one index can still leave GCD 1.

So for each position i, we compute:

gcd(values on the left of i, values on the right of i)

If that value is 1 for at least one index, then a good subsequence exists.

Why a segment tree fits well

We need two operations repeatedly:

• point update after each query
• range GCD query

A segment tree supports both in O(log n).

That gives us:

• build in O(n)
• each update in O(log n)
• each left/right GCD check in O(log n)

The implementation is very direct:

• leaf = transformed value at that index
• internal node = GCD of its two children

Approach

For every query:

1. remove the old contribution from cnt
2. update the array and the segment tree
3. add the new contribution back to cnt
4. if cnt == 0, skip
5. if overall reduced GCD is not 1, skip
6. if cnt < n, count this query
7. otherwise try removing one index, and count the query if any remaining GCD is 1

Why the transformed GCD works

Suppose a subsequence contains only values divisible by p:

a1 = p * b1
a2 = p * b2
...
ak = p * bk

Then:

gcd(a1, a2, ..., ak) = p * gcd(b1, b2, ..., bk)

So asking for original GCD exactly p is the same as asking for reduced GCD exactly 1.

That is the whole reason the reduction works.

class Solution {
    private int n;
    private int p;
    private int[] arr;
    private int[] seg;

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return Math.abs(a);
    }

    private int valueAt(int value) {
        return value % p == 0 ? value / p : 0;
    }

    private void build(int idx, int left, int right) {
        if (left == right) {
            seg[idx] = valueAt(arr[left]);
            return;
        }

        int mid = (left + right) >>> 1;
        build(idx << 1, left, mid);
        build(idx << 1 | 1, mid + 1, right);
        seg[idx] = gcd(seg[idx << 1], seg[idx << 1 | 1]);
    }

    private void update(int idx, int left, int right, int pos, int value) {
        if (left == right) {
            arr[left] = value;
            seg[idx] = valueAt(value);
            return;
        }

        int mid = (left + right) >>> 1;
        if (pos <= mid) {
            update(idx << 1, left, mid, pos, value);
        } else {
            update(idx << 1 | 1, mid + 1, right, pos, value);
        }

        seg[idx] = gcd(seg[idx << 1], seg[idx << 1 | 1]);
    }

    private int query(int idx, int left, int right, int ql, int qr) {
        if (qr < left || right < ql) {
            return 0;
        }
        if (ql <= left && right <= qr) {
            return seg[idx];
        }

        int mid = (left + right) >>> 1;
        return gcd(
            query(idx << 1, left, mid, ql, qr),
            query(idx << 1 | 1, mid + 1, right, ql, qr)
        );
    }

    public int countGoodSubseq(int[] nums, int pp, int[][] queries) {
        n = nums.length;
        p = pp;
        arr = nums.clone();
        seg = new int[n << 2];

        build(1, 0, n - 1);

        int cnt = 0;
        for (int value : arr) {
            if (value % p == 0) {
                cnt++;
            }
        }

        int answer = 0;

        for (int[] query : queries) {
            int index = query[0];
            int value = query[1];

            if (arr[index] % p == 0) {
                cnt--;
            }

            update(1, 0, n - 1, index, value);

            if (arr[index] % p == 0) {
                cnt++;
            }

            if (cnt == 0 || seg[1] != 1) {
                continue;
            }

            if (cnt < n) {
                answer++;
                continue;
            }

            boolean ok = false;
            for (int i = 0; i < n; i++) {
                int currentGcd = 0;

                if (i > 0) {
                    currentGcd = gcd(currentGcd, query(1, 0, n - 1, 0, i - 1));
                }
                if (i + 1 < n) {
                    currentGcd = gcd(currentGcd, query(1, 0, n - 1, i + 1, n - 1));
                }

                if (currentGcd == 1) {
                    ok = true;
                    break;
                }
            }

            if (ok) {
                answer++;
            }
        }

        return answer;
    }
}

Walkthrough

Take:

nums = [4, 8, 12, 16]
p = 2

The reduced usable values are:

[2, 4, 6, 8]

Now apply the first query [0, 3]:

nums = [3, 8, 12, 16]
reduced = [0, 4, 6, 8]

Only the divisible elements matter, and their GCD is:

gcd(4, 6, 8) = 2

So there is no subsequence with reduced GCD 1, which means no subsequence with original GCD 2.

Now apply the second query [2, 6]:

nums = [3, 8, 6, 16]
reduced = [0, 4, 3, 8]

The usable values now have GCD:

gcd(4, 3, 8) = 1

Since index 0 is unusable, taking all usable values is already a proper subsequence.

That corresponds to original subsequence [8, 6, 16], whose GCD is exactly 2.

Complexity analysis

Time Complexity: O(q * log n) in practice

• each point update takes O(log n)
• each GCD range query takes O(log n)
• the expensive loop over removals only matters in the cnt == n and overall-GCD-1 case

The subtle part is why that last loop does not blow up in practice.

If removing index i makes the remaining GCD larger than 1, then every remaining element shares some prime factor that nums[i] / p is missing.

So each such critical index can be associated with a distinct missing prime factor.

Because every value is at most 5 * 10^4, the number of distinct prime factors involved is very small. That keeps the number of genuinely relevant indices small, so the full solution behaves like O(q * log n).

Space Complexity: O(n)

• the segment tree uses O(n)
• the current array also uses O(n)

Edge cases to remember

1. All elements are not divisible by p

Then cnt == 0, so the answer is immediately false.

2. Overall reduced GCD is not 1

Then no usable subsequence can have reduced GCD 1, because every subsequence GCD must be a multiple of the overall GCD.

3. All elements are divisible by p

Then we cannot take the whole array, so we must explicitly test whether removing one index still leaves GCD 1.

Why I like this problem

This is a good example of a hard query problem that becomes much cleaner after the right reduction.

At first it looks like a dynamic subsequence problem. But after dividing everything by p, it turns into:

• maintain usable elements
• maintain their GCD
• handle the full-array corner case carefully

That is a much more manageable way to think about it.

Related problems

• Subarray GCD — Hard
• Range GCD Queries — Medium
• Product of Array Except Self — Medium