3655. XOR After Range Multiplication Queries II

HardArrayDivide and Conquer

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums of length n and a 2D integer array queries of size q, where each query is represented as queries[i] = [li, ri, ki, vi].

For each query, you must perform a sequence of update operations on the array. The procedure works as follows:

Start by setting an index pointer idx = li.
Then, repeatedly do the following while idx <= ri:
- Multiply the value at position idx by vi, taking the result modulo 10^9 + 7. In other words, update nums[idx] = (nums[idx] * vi) % (10^9 + 7).
- Advance the pointer by ki, that is idx += ki.

In simpler terms, for a given query you walk through the array starting at index li, stepping forward ki positions at a time, and you keep going as long as you don't pass index ri. At every position you visit, you scale the stored value by vi under modular arithmetic.

After all q queries have been processed one after another, return the bitwise XOR of every element in the final nums array.

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.

The problem uses square root decomposition on step size k: small-step queries are batched via arithmetic progression updates, large-step queries are simulated directly.

Open in Flowchart

Intuition

The most direct way to solve this problem is to simulate every query exactly as described: for each query, walk from li to ri in steps of ki and multiply each visited element by vi. The trouble is that when the step ki is small (for example ki = 1), a single query can touch almost the entire array, and with many such queries the total work can become as large as O(q * n), which is too slow.

The key observation is that the cost of a query depends on its step size k. A query with a large step only touches a few positions (at most n / k), so simulating it directly is cheap. A query with a small step can touch many positions, so simulating it directly is expensive. This natural split suggests a square root decomposition on the step size k:

If k > sqrt(n), the query visits at most sqrt(n) positions, so we just apply it directly. The total cost of all such queries is bounded.
If k <= sqrt(n), we cannot afford to walk each query individually. Instead, we need a smarter way to batch these updates.

For the small-step case, the trick is to notice that all positions touched by a query with step k and start l share the same remainder res = l % k. In other words, the array splits into k independent arithmetic progressions (one per remainder), and a query only multiplies a contiguous range of terms inside one of these progressions.

Multiplying a contiguous range by a value v is exactly the kind of operation we can handle with a difference-array style technique, but for products instead of sums. To "open" the range we multiply by v at the start term, and to "close" it we multiply by the modular inverse v^(-1) just past the end term. By sweeping through the progression while keeping a running product cur, every term automatically gets multiplied by the product of all queries that currently "cover" it.

The reason division works here is that we are operating under a prime modulus 10^9 + 7, so every non-zero v has a modular inverse pow(v, MOD - 2, MOD) (by Fermat's little theorem). This lets us undo a multiplication just like subtraction undoes addition in an ordinary difference array.

So the plan becomes:

Group small-step queries by their (k, remainder) bucket, recording a multiply event at the start term and an inverse event one step past the end term.
For each bucket, sort the events by their term index, sweep through the progression maintaining a running product, and apply that product to each element.
Handle large-step queries by brute force.
Finally, XOR all elements together.

This balances the two extremes: large steps are cheap to brute force, and small steps are handled efficiently by the product difference-array, giving an overall complexity around O((n + q) * sqrt(n)).

Pattern Learn more about Divide and Conquer patterns.

Solution Approach

The implementation follows the square root decomposition idea. Let n be the length of nums, MOD = 10^9 + 7, and choose a block size B = isqrt(n) + 1. Queries with step k > B are handled directly, while queries with k <= B are batched.

1. The events container

We build a nested list events, where events[k][res] holds the multiply/divide events for the arithmetic progression with step k and remainder res:

events = [[[] for _ in range(k)] for k in range(B + 1)]

For a fixed k, there are exactly k possible remainders, so events[k] has k slots. Each slot stores a list of (t, v) pairs, where t is the term index within the progression and v is the value to multiply by.

2. Distributing the queries

For each query [l, r, k, v]:

Large step (k > B): simply walk the indices and apply the multiplication directly. Because k > sqrt(n), this loop runs at most sqrt(n) times.

if k > B:
    for idx in range(l, r + 1, k):
        nums[idx] = nums[idx] * v % MOD

Small step (k <= B): convert the range update into two events on the progression. All visited indices share the remainder res = l % k. The term indices range from t1 = (l - res) // k to t2 = (r - res) // k. We record a multiply event at t1:

res = l % k
t1 = (l - res) // k
t2 = (r - res) // k
events[k][res].append((t1, v))

To "close" the range, we multiply by the modular inverse v^(-1) one term past t2, but only if that term actually exists in the array (the guard t2 + 1 <= (n - 1 - res) // k):

if t2 + 1 <= (n - 1 - res) // k:
    invv = pow(v, MOD - 2, MOD)
    events[k][res].append((t2 + 1, invv))

The inverse is computed with Fermat's little theorem via pow(v, MOD - 2, MOD), valid because MOD is prime.

3. Sweeping each progression

After all queries are distributed, we process every bucket events[k][res]:

First, sort the events by term index, then compress events that fall on the same term by combining their values into a single product. This avoids reapplying at the same point multiple times:

ev.sort()
comp = []
for t, val in ev:
    if comp and comp[-1][0] == t:
        comp[-1] = (t, comp[-1][1] * val % MOD)
    else:
        comp.append([t, val])

Then we walk through the progression term by term (idx = res, res + k, res + 2k, ...), keeping a running product cur. Whenever the current term t matches the next event's term, we fold that event into cur. Every element is then multiplied by cur, which represents the combined effect of all queries currently covering this term:

cur = 1
ptr = 0
t = 0
idx = res
while idx < n:
    while ptr < len(comp) and comp[ptr][0] == t:
        cur = cur * comp[ptr][1] % MOD
        ptr += 1
    nums[idx] = nums[idx] * cur % MOD
    idx += k
    t += 1

This is the product difference-array in action: the multiply event at t1 switches a factor "on", and the inverse event at t2 + 1 switches it back "off", so only terms in [t1, t2] keep that factor.

4. Final answer

Once all buckets are processed and large-step queries applied, XOR every element together:

xr = 0
for x in nums:
    xr ^= x
return xr

Complexity

Each large-step query costs O(sqrt(n)), so all of them together cost O(q * sqrt(n)).
Small-step queries add at most 2 events each, and sweeping all progressions for a given k visits every array index once, costing O(n) per value of k up to B. Combined with sorting the events, the total is roughly O((n + q) * sqrt(n) + q * log q).
Space is O(n + q) for the events and the array.

Example Walkthrough

Let's trace through a small example to see how the square root decomposition and product difference-array work together.

Setup

nums    = [2, 3, 1, 4, 5, 6]   (n = 6)
queries = [[0, 4, 1, 2],        // l=0, r=4, k=1, v=2
           [1, 5, 4, 3]]        // l=1, r=5, k=4, v=3
MOD     = 10^9 + 7
B       = isqrt(6) + 1 = 3      // block size threshold

Because B = 3, any query with step k > 3 is brute-forced, and any query with k <= 3 is batched into events.

Step 1 — Classify the queries

Query 1: k = 1, and 1 <= 3, so it is a small-step query → batch via events.
Query 2: k = 4, and 4 > 3, so it is a large-step query → apply directly.

Step 2 — Handle the large-step query directly (Query 2)

We walk from l = 1 to r = 5 in steps of k = 4, multiplying by v = 3:

idx = 1: nums[1] = 3 * 3 = 9
idx = 5: nums[5] = 6 * 3 = 18
idx = 9 → exceeds r, stop.

This loop runs only 2 times (at most n / k), confirming large steps are cheap.

nums = [2, 9, 1, 4, 5, 18]

Step 3 — Build events for the small-step query (Query 1)

Query 1 has l = 0, r = 4, k = 1, v = 2. With step 1, the remainder is:

res = l % k = 0 % 1 = 0
t1  = (l - res) / k = (0 - 0) / 1 = 0      // first term index
t2  = (r - res) / k = (4 - 0) / 1 = 4      // last term index

We record a multiply event at term t1 = 0:

events[1][0] = [(0, 2)]

To "close" the range, we add an inverse event one term past t2, but only if that term exists. The largest valid term is (n - 1 - res) / k = 5, and t2 + 1 = 5 <= 5, so it exists. The inverse of 2 is pow(2, MOD-2, MOD) = invv:

events[1][0] = [(0, 2), (5, invv)]

Intuitively: term 0 switches the factor ×2 on, and term 5 switches it back off, so only terms [0, 4] keep the factor — exactly the queried range.

Step 4 — Sweep the progression (k=1, res=0)

Sort and compress events (no duplicate term indices here):

comp = [[0, 2], [5, invv]]

Now walk through every term idx = 0, 1, 2, 3, 4, 5 keeping a running product cur:

term `t`	`idx`	event fires?	`cur`	`nums[idx]` before → after
0	0	yes, `cur = 1*2 = 2`	2	2 → `2*2 = 4`
1	1	no	2	9 → `9*2 = 18`
2	2	no	2	1 → `1*2 = 2`
3	3	no	2	4 → `4*2 = 8`
4	4	no	2	5 → `5*2 = 10`
5	5	yes, `cur=2*invv=1`	1	18 → `18*1 = 18`

Notice how the inverse event at term 5 restores cur to 1, leaving nums[5] untouched — precisely because index 5 was outside [0, 4].

nums = [4, 18, 2, 8, 10, 18]

Step 5 — Verify against brute force

Directly simulating both queries on the original [2, 3, 1, 4, 5, 6]:

Query 1 (×2 on indices 0–4): [4, 6, 2, 8, 10, 6]
Query 2 (×3 on indices 1, 5): [4, 18, 2, 8, 10, 18] ✓

The results match.

Step 6 — Final XOR

4 ^ 18 ^ 2 ^ 8 ^ 10 ^ 18
= (4 ^ 18) = 22
22 ^ 2     = 20
20 ^ 8     = 28
28 ^ 10    = 22
22 ^ 18    = 4

Answer: 4

This small trace shows both halves of the strategy: the large-step query was cheaply simulated, while the small-step query was converted into a pair of on/off events and resolved in a single sweep using the running product.

Solution Implementation

1import math
2from typing import List
3
4
5class Solution:
6    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
7        MOD = 1_000_000_007
8        n = len(nums)
9
10        # Block size threshold for the sqrt decomposition strategy.
11        # Queries with step > block_size are handled directly (few iterations),
12        # while queries with step <= block_size are batched via difference arrays.
13        block_size = int(math.isqrt(n)) + 1
14
15        # events[step][residue] holds a list of (time_index, value) pairs.
16        # For each (step, residue), the indices l, l+step, l+2*step, ... form a
17        # subsequence; "time_index" is the position within that subsequence.
18        # We use a difference-array style technique on multiplication:
19        # multiply at the start time, and divide (multiply by inverse) right
20        # after the end time, so prefix-products give the effective multiplier.
21        events = [[[] for _ in range(step)] for step in range(block_size + 1)]
22
23        for left, right, step, value in queries:
24            if step > block_size:
25                # Large step: directly apply multiplication to each affected index.
26                for idx in range(left, right + 1, step):
27                    nums[idx] = nums[idx] * value % MOD
28            else:
29                # Small step: record the range as difference-array events.
30                residue = left % step
31                start_time = (left - residue) // step
32                end_time = (right - residue) // step
33
34                # Open the multiplication interval at start_time.
35                events[step][residue].append((start_time, value))
36
37                # Close the interval right after end_time by applying the inverse,
38                # but only if there is still an index beyond the range to affect.
39                last_time = (n - 1 - residue) // step
40                if end_time + 1 <= last_time:
41                    inverse_value = pow(value, MOD - 2, MOD)
42                    events[step][residue].append((end_time + 1, inverse_value))
43
44        # Process all batched (small-step) events.
45        for step in range(1, block_size + 1):
46            for residue in range(step):
47                event_list = events[step][residue]
48                if not event_list:
49                    continue
50
51                # Sort events by time so we can sweep them in order.
52                event_list.sort()
53
54                # Compress events that share the same time index by combining
55                # their multipliers, producing a clean list of [time, product].
56                compressed = []
57                for time_index, val in event_list:
58                    if compressed and compressed[-1][0] == time_index:
59                        compressed[-1][1] = compressed[-1][1] * val % MOD
60                    else:
61                        compressed.append([time_index, val])
62
63                # Sweep through the subsequence indices residue, residue+step, ...
64                # maintaining a running product of all active multipliers.
65                current_multiplier = 1
66                ptr = 0
67                time_index = 0
68                idx = residue
69                while idx < n:
70                    # Apply all events scheduled at the current time index.
71                    while ptr < len(compressed) and compressed[ptr][0] == time_index:
72                        current_multiplier = current_multiplier * compressed[ptr][1] % MOD
73                        ptr += 1
74                    nums[idx] = nums[idx] * current_multiplier % MOD
75                    idx += step
76                    time_index += 1
77
78        # Compute the final XOR of all transformed values.
79        result = 0
80        for value in nums:
81            result ^= value
82        return result
83

1class Solution {
2    // Modulus for all multiplicative operations
3    static final int kMod = 1000000007;
4
5    // Fast modular exponentiation: computes (base^exp) % kMod
6    private long ModPow(long base, long exp) {
7        long result = 1 % kMod;
8        base %= kMod;
9        while (exp > 0) {
10            // If the current lowest bit is set, multiply result by current base
11            if ((exp & 1) == 1) {
12                result = (result * base) % kMod;
13            }
14            // Square the base and shift exponent right
15            base = (base * base) % kMod;
16            exp >>= 1;
17        }
18        return result;
19    }
20
21    public int xorAfterQueries(int[] nums, int[][] queries) {
22        int n = nums.length;
23        // Threshold for the square-root decomposition.
24        // Strides larger than blockSize are handled directly (brute force),
25        // strides up to blockSize are handled via a difference-array technique.
26        int blockSize = (int) Math.sqrt(n) + 1;
27
28        // events[k][residue] stores (time, multiplier) pairs for stride k
29        // and starting residue (index % k). "time" is the position within the
30        // arithmetic progression starting at the residue.
31        List<List<List<int[]>>> events = new ArrayList<>(blockSize + 1);
32        for (int k = 0; k <= blockSize; ++k) {
33            events.add(new ArrayList<>());
34        }
35        for (int k = 1; k <= blockSize; ++k) {
36            // For stride k there are exactly k possible residue classes.
37            for (int residue = 0; residue < k; ++residue) {
38                events.get(k).add(new ArrayList<>());
39            }
40        }
41
42        for (int[] query : queries) {
43            int left = query[0];
44            int right = query[1];
45            int stride = query[2];
46            int value = query[3];
47
48            if (stride > blockSize) {
49                // Large stride: few touched indices, apply multiplications directly.
50                for (int idx = left; idx <= right; idx += stride) {
51                    nums[idx] = (int) ((long) nums[idx] * value % kMod);
52                }
53            } else {
54                // Small stride: use a multiplicative difference array.
55                // Determine the residue class and the time indices for left/right.
56                int residue = left % stride;
57                int startTime = (left - residue) / stride;
58                int endTime = (right - residue) / stride;
59
60                // Multiply by value starting from startTime.
61                events.get(stride).get(residue).add(new int[] {startTime, value});
62
63                // Cancel the multiplication after endTime by multiplying with the
64                // modular inverse, but only if there is a valid next position.
65                if (endTime + 1 <= (n - 1 - residue) / stride) {
66                    int inverseValue = (int) ModPow(value, kMod - 2);
67                    events.get(stride).get(residue).add(new int[] {endTime + 1, inverseValue});
68                }
69            }
70        }
71
72        // Process all small strides via the difference-array approach.
73        for (int k = 1; k <= blockSize; ++k) {
74            for (int residue = 0; residue < k; ++residue) {
75                List<int[]> currentEvents = events.get(k).get(residue);
76                if (currentEvents.isEmpty()) {
77                    continue;
78                }
79
80                // Sort events by time so we can sweep through them in order.
81                currentEvents.sort((a, b) -> Integer.compare(a[0], b[0]));
82
83                // Compress events that share the same time into a single multiplier.
84                List<int[]> compressed = new ArrayList<>();
85                for (int[] event : currentEvents) {
86                    if (!compressed.isEmpty() && compressed.get(compressed.size() - 1)[0] == event[0]) {
87                        int[] last = compressed.get(compressed.size() - 1);
88                        last[1] = (int) ((long) last[1] * event[1] % kMod);
89                    } else {
90                        compressed.add(event);
91                    }
92                }
93
94                // Sweep through the arithmetic progression, maintaining the running
95                // cumulative multiplier and applying it to each element.
96                long cumulative = 1;
97                int ptr = 0;
98                int time = 0;
99                for (int idx = residue; idx < n; idx += k, ++time) {
100                    while (ptr < compressed.size() && compressed.get(ptr)[0] == time) {
101                        cumulative = (cumulative * compressed.get(ptr)[1]) % kMod;
102                        ++ptr;
103                    }
104                    nums[idx] = (int) (nums[idx] * cumulative % kMod);
105                }
106            }
107        }
108
109        // Compute the XOR of all final values.
110        int xorResult = 0;
111        for (int value : nums) {
112            xorResult ^= value;
113        }
114
115        return xorResult;
116    }
117}
118

1class Solution {
2    // Modulus for all multiplicative operations
3    static constexpr int kMod = 1000000007;
4
5    // Fast modular exponentiation: computes (base^exp) % kMod
6    long long ModPow(long long base, long long exp) {
7        long long result = 1 % kMod;
8        base %= kMod;
9        while (exp > 0) {
10            // If the current lowest bit is set, multiply result by current base
11            if (exp & 1) {
12                result = (result * base) % kMod;
13            }
14            // Square the base and shift exponent right
15            base = (base * base) % kMod;
16            exp >>= 1;
17        }
18        return result;
19    }
20
21public:
22    int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
23        int n = nums.size();
24        // Threshold for the square-root decomposition.
25        // Strides larger than blockSize are handled directly (brute force),
26        // strides up to blockSize are handled via a difference-array technique.
27        int blockSize = sqrt(n) + 1;
28
29        // events[k][residue] stores (time, multiplier) pairs for stride k
30        // and starting residue (index % k). "time" is the position within the
31        // arithmetic progression starting at the residue.
32        vector<vector<vector<pair<int, int>>>> events(blockSize + 1);
33        for (int k = 1; k <= blockSize; ++k) {
34            events[k].resize(k);
35        }
36
37        for (auto& query : queries) {
38            int left = query[0];
39            int right = query[1];
40            int stride = query[2];
41            int value = query[3];
42
43            if (stride > blockSize) {
44                // Large stride: few touched indices, apply multiplications directly.
45                for (int idx = left; idx <= right; idx += stride) {
46                    nums[idx] = static_cast<long long>(nums[idx]) * value % kMod;
47                }
48            } else {
49                // Small stride: use a multiplicative difference array.
50                // Determine the residue class and the time indices for left/right.
51                int residue = left % stride;
52                int startTime = (left - residue) / stride;
53                int endTime = (right - residue) / stride;
54
55                // Multiply by value starting from startTime.
56                events[stride][residue].push_back({startTime, value});
57
58                // Cancel the multiplication after endTime by multiplying with the
59                // modular inverse, but only if there is a valid next position.
60                if (endTime + 1 <= (n - 1 - residue) / stride) {
61                    int inverseValue = ModPow(value, kMod - 2);
62                    events[stride][residue].push_back({endTime + 1, inverseValue});
63                }
64            }
65        }
66
67        // Process all small strides via the difference-array approach.
68        for (int k = 1; k <= blockSize; ++k) {
69            for (int residue = 0; residue < k; ++residue) {
70                auto& currentEvents = events[k][residue];
71                if (currentEvents.empty()) {
72                    continue;
73                }
74
75                // Sort events by time so we can sweep through them in order.
76                sort(currentEvents.begin(), currentEvents.end());
77
78                // Compress events that share the same time into a single multiplier.
79                vector<pair<int, int>> compressed;
80                for (auto& event : currentEvents) {
81                    if (!compressed.empty() && compressed.back().first == event.first) {
82                        compressed.back().second =
83                            static_cast<long long>(compressed.back().second) * event.second % kMod;
84                    } else {
85                        compressed.push_back(event);
86                    }
87                }
88
89                // Sweep through the arithmetic progression, maintaining the running
90                // cumulative multiplier and applying it to each element.
91                long long cumulative = 1;
92                int ptr = 0;
93                int time = 0;
94                for (int idx = residue; idx < n; idx += k, ++time) {
95                    while (ptr < static_cast<int>(compressed.size()) &&
96                           compressed[ptr].first == time) {
97                        cumulative = (cumulative * compressed[ptr].second) % kMod;
98                        ++ptr;
99                    }
100                    nums[idx] = nums[idx] * cumulative % kMod;
101                }
102            }
103        }
104
105        // Compute the XOR of all final values.
106        int xorResult = 0;
107        for (int value : nums) {
108            xorResult ^= value;
109        }
110
111        return xorResult;
112    }
113};
114

1// Modulus for all multiplicative operations
2const kMod = 1000000007n;
3
4/**
5 * Fast modular exponentiation: computes (base^exp) % kMod
6 * Uses BigInt to avoid overflow during multiplication.
7 */
8function ModPow(base: bigint, exp: bigint): bigint {
9    let result = 1n % kMod;
10    base %= kMod;
11    while (exp > 0n) {
12        // If the current lowest bit is set, multiply result by current base
13        if (exp & 1n) {
14            result = (result * base) % kMod;
15        }
16        // Square the base and shift exponent right
17        base = (base * base) % kMod;
18        exp >>= 1n;
19    }
20    return result;
21}
22
23function xorAfterQueries(nums: number[], queries: number[][]): number {
24    const n = nums.length;
25    // Threshold for the square-root decomposition.
26    // Strides larger than blockSize are handled directly (brute force),
27    // strides up to blockSize are handled via a difference-array technique.
28    const blockSize = Math.floor(Math.sqrt(n)) + 1;
29
30    // Work on a BigInt copy to safely perform modular multiplications.
31    const values: bigint[] = nums.map((value) => BigInt(value));
32
33    // events[k][residue] stores [time, multiplier] pairs for stride k
34    // and starting residue (index % k). "time" is the position within the
35    // arithmetic progression starting at the residue.
36    const events: Array<Array<Array<[number, bigint]>>> = new Array(blockSize + 1);
37    for (let k = 1; k <= blockSize; ++k) {
38        events[k] = new Array(k);
39        for (let residue = 0; residue < k; ++residue) {
40            events[k][residue] = [];
41        }
42    }
43
44    for (const query of queries) {
45        const left = query[0];
46        const right = query[1];
47        const stride = query[2];
48        const value = BigInt(query[3]);
49
50        if (stride > blockSize) {
51            // Large stride: few touched indices, apply multiplications directly.
52            for (let idx = left; idx <= right; idx += stride) {
53                values[idx] = (values[idx] * value) % kMod;
54            }
55        } else {
56            // Small stride: use a multiplicative difference array.
57            // Determine the residue class and the time indices for left/right.
58            const residue = left % stride;
59            const startTime = (left - residue) / stride;
60            const endTime = (right - residue) / stride;
61
62            // Multiply by value starting from startTime.
63            events[stride][residue].push([startTime, value]);
64
65            // Cancel the multiplication after endTime by multiplying with the
66            // modular inverse, but only if there is a valid next position.
67            if (endTime + 1 <= Math.floor((n - 1 - residue) / stride)) {
68                const inverseValue = ModPow(value, kMod - 2n);
69                events[stride][residue].push([endTime + 1, inverseValue]);
70            }
71        }
72    }
73
74    // Process all small strides via the difference-array approach.
75    for (let k = 1; k <= blockSize; ++k) {
76        for (let residue = 0; residue < k; ++residue) {
77            const currentEvents = events[k][residue];
78            if (currentEvents.length === 0) {
79                continue;
80            }
81
82            // Sort events by time so we can sweep through them in order.
83            currentEvents.sort((a, b) => a[0] - b[0]);
84
85            // Compress events that share the same time into a single multiplier.
86            const compressed: Array<[number, bigint]> = [];
87            for (const event of currentEvents) {
88                if (
89                    compressed.length > 0 &&
90                    compressed[compressed.length - 1][0] === event[0]
91                ) {
92                    compressed[compressed.length - 1][1] =
93                        (compressed[compressed.length - 1][1] * event[1]) % kMod;
94                } else {
95                    compressed.push([event[0], event[1]]);
96                }
97            }
98
99            // Sweep through the arithmetic progression, maintaining the running
100            // cumulative multiplier and applying it to each element.
101            let cumulative = 1n;
102            let ptr = 0;
103            let time = 0;
104            for (let idx = residue; idx < n; idx += k, ++time) {
105                while (ptr < compressed.length && compressed[ptr][0] === time) {
106                    cumulative = (cumulative * compressed[ptr][1]) % kMod;
107                    ++ptr;
108                }
109                values[idx] = (values[idx] * cumulative) % kMod;
110            }
111        }
112    }
113
114    // Compute the XOR of all final values.
115    let xorResult = 0;
116    for (const value of values) {
117        xorResult ^= Number(value);
118    }
119
120    return xorResult;
121}
122

Time and Space Complexity

Time Complexity

Let n = len(nums), q = len(queries), and B = ⌊√n⌋ + 1.

1. Processing queries:

For each query (l, r, k, v):

Heavy case (k > B): We directly iterate over indices l, l+k, l+2k, ... up to r. Since k > B ≈ √n, the number of iterations is at most r/k < n/√n = √n. So each heavy query costs O(√n), totaling O(q·√n) in the worst case.
Light case (k ≤ B): We do O(1) work, appending at most two events (the modular inverse pow(v, MOD-2, MOD) is O(log MOD)). So light queries cost O(q·log MOD) total.

Combined: O(q·√n + q·log MOD).

2. Processing events (light queries):

The events are bucketed in events[k][res]. Each light query contributes at most 2 events, so the total number of events across all buckets is O(q).

For each bucket (k, res):

Sorting: Each bucket's events are sorted; summed over all buckets this is O(q·log q) in the worst case (all events could fall in one bucket).
Compression: Linear in the number of events, O(q) total.
Sweeping the arithmetic sequence: For a fixed k, iterating over all residues res = 0..k-1 covers each array index exactly once. So the sweep over one full k value costs O(n). Summing over all k from 1 to B gives O(B·n) = O(n·√n) = O(n^{1.5}).

So event processing is O(n^{1.5} + q·log q).

3. Final XOR: O(n).

Overall time complexity:

O(n^{1.5} + q·√n + q·log q + q·log MOD)

which simplifies to roughly O((n + q)·√n + q·log q).

Space Complexity

The events structure has B + 1 rows, where row k has k residue lists, giving O(1 + 2 + ... + B) = O(B²) = O(n) empty list overhead for the buckets.
The total number of stored event tuples is O(q).
The compressed list comp and other auxiliary variables use O(q) in the worst case.

Overall space complexity: O(n + q).

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

Common Pitfalls

Pitfall: Closing the difference-array interval at the wrong time index (or skipping the bounds guard)

The trickiest part of this solution is the product difference-array logic. A query [l, r, k, v] should multiply v into terms t1 = (l - res) // k through t2 = (r - res) // k of the progression (where res = l % k). The technique is:

Multiply by v at term t1 (turn the factor on).
Multiply by v⁻¹ at term t2 + 1 (turn the factor off).

Two mistakes commonly arise here:

Mistake A — Forgetting the existence guard on the "close" event.

If t2 is the last term of the progression that fits in the array, then t2 + 1 corresponds to an index res + (t2 + 1) * k that is >= n. The sweep loop (while idx < n) will never reach that term, so the inverse event never gets applied. By itself that's harmless — the factor simply stays "on" for terms that don't exist. The danger is the opposite: if you blindly insert the inverse event without the guard, and then for some other query a real term happens to land exactly on t2 + 1, the spurious inverse gets folded into current_multiplier and silently corrupts the result. The guard

last_time = (n - 1 - residue) // step
if end_time + 1 <= last_time:
    ...append the inverse...

ensures the close event is only recorded when that term actually exists in the array.

Mistake B — Using modular subtraction/division naively instead of an inverse.

A frequent instinct is to "undo" a multiplication with integer division (nums[idx] // v) or to track sums with a plain difference array and subtraction. Both are wrong under modular arithmetic:

(a * v) % MOD // v is not a, because the modulo already collapsed the value.
Multiplication does not distribute over a subtractive difference array the way addition does.

The correct "inverse" is the modular multiplicative inverse via Fermat's little theorem, pow(v, MOD - 2, MOD), valid because MOD = 10⁹ + 7 is prime. This works only when v is not a multiple of MOD (always true for the given constraints, since v < MOD).

Solution

Keep both safeguards explicit and verify them together. Here is a small self-check you can run to confirm the difference-array closing logic matches a brute-force simulation:

def brute(nums, queries, MOD=1_000_000_007):
    nums = nums[:]
    for l, r, k, v in queries:
        idx = l
        while idx <= r:
            nums[idx] = nums[idx] * v % MOD
            idx += k
    xr = 0
    for x in nums:
        xr ^= x
    return xr

# Example that specifically exercises the boundary:
# a query whose t2 is the LAST term, and another query landing on t2+1.
nums = [1, 1, 1, 1, 1, 1]
queries = [
    [0, 4, 2, 3],   # touches indices 0,2,4 ; t2 = 2 is the last term (idx 4)
    [0, 4, 2, 5],   # same progression, overlapping
]
assert Solution().xorAfterQueries(nums[:], [q[:] for q in queries]) == brute(nums, queries)

Key takeaways for avoiding the pitfall:

Always gate the close event with end_time + 1 <= (n - 1 - residue) // step. Omitting it can corrupt unrelated terms of the same progression; adding an unconditional close that lands out of range is wasted work at best and a bug at worst.
Never use integer division or subtraction to reverse a modular multiply. Precompute pow(v, MOD - 2, MOD) and multiply by it instead.
Compress events on the same term before sweeping. If two queries open at the same t1, their factors must be folded into a single combined multiplier; otherwise a later inverse that assumes a single fold could mismatch. The compression step (combining (t, val) pairs with equal t) keeps the on/off bookkeeping consistent.
Validate against brute force on small random inputs, paying special attention to cases where a range ends exactly at the final reachable term of its progression — that's precisely where the boundary guard matters.

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:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don't know