3653. XOR After Range Multiplication Queries I

MediumArrayDivide and ConquerSimulation

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 queries[i] = [l_i, r_i, k_i, v_i].

For each query, you need to perform a series of updates on the array nums following these steps in order:

Start by setting an index idx = l_i.
Then, repeatedly do the following while idx <= r_i:
- Multiply the current element by v_i and take the result modulo 10^9 + 7, i.e., nums[idx] = (nums[idx] * v_i) % (10^9 + 7).
- Move the index forward by k_i, i.e., idx += k_i.

In simple terms, each query updates the elements at positions l_i, l_i + k_i, l_i + 2*k_i, and so on, as long as the position does not exceed r_i. Every one of these elements is multiplied by v_i (with the modulo applied to keep the values within range).

After processing all the queries one by one, you must return the bitwise XOR of all the elements in the final array nums.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

The problem directly simulates range multiplication queries with a fixed step size, then computes the XOR of all elements.

Open in Flowchart

Intuition

The problem describes exactly what we need to do step by step, so the most natural way to solve it is to simulate the process directly.

Looking closely at the operations, each query asks us to walk through the array starting at index l_i, jumping forward by k_i each time, and stopping once we go past r_i. At every position we land on, we multiply the value by v_i and apply the modulo. This is precisely the behavior of a stepped range — going from l_i to r_i in increments of k_i — which maps perfectly to a loop like range(l, r + 1, k).

Since there is no hidden trick or special pattern to exploit, we can simply follow the instructions: for each query, iterate over the affected indices and update them in place. The modulo 10^9 + 7 is applied after every multiplication to prevent the numbers from growing too large.

Once all queries have been applied and the array reflects its final state, the last requirement is to combine all elements using the bitwise XOR. We can accomplish this by folding the XOR operation across the entire array, which gives us the single integer answer the problem asks for.

Pattern Learn more about Divide and Conquer patterns.

Solution Approach

Solution 1: Simulation

We directly simulate the operations described in the problem by processing each query in turn and updating the corresponding elements in the array nums. Finally, we compute the bitwise XOR of all elements and return the result.

The implementation works as follows:

First, define the modulo constant mod = 10^9 + 7, which we use to keep the values within range after each multiplication.
Iterate over every query, unpacking it into its four parts l, r, k, v:
- For each query, use range(l, r + 1, k) to generate the affected indices. This starts at l, steps forward by k each time, and stops once the index exceeds r, which exactly matches the while idx <= r loop described in the problem.
- For each index idx produced by this range, update the value with nums[idx] = nums[idx] * v % mod.
After all queries have been applied, the array nums holds its final state. We then combine all elements using the bitwise XOR. In the code, reduce(xor, nums) folds the xor operation across the entire array, producing a single integer that is the answer.

Let n be the length of nums, q be the number of queries, and the loop inside each query touches at most O(n / k) elements. In the worst case (k = 1), each query may scan the whole array, so the overall time complexity is O(n + q * n). The space complexity is O(1), since we update the array in place and only use a constant amount of extra space.

Example Walkthrough

Let's trace through a small concrete example to see how the simulation works.

Input:

nums = [1, 2, 3, 4, 5] (so n = 5)
queries = [[0, 4, 2, 3], [1, 3, 1, 2]]
mod = 10^9 + 7

Processing Query 1: [l=0, r=4, k=2, v=3]

We generate indices using range(0, 4 + 1, 2), which gives 0, 2, 4. At each index, we multiply by v = 3 and apply the modulo:

idx	Before	Calculation	After
0	1	`(1 * 3) % mod`	3
2	3	`(3 * 3) % mod`	9
4	5	`(5 * 3) % mod`	15

Array after Query 1: [3, 2, 9, 4, 15]

Notice that indices 1 and 3 are untouched because the step k = 2 jumps right over them.

Processing Query 2: [l=1, r=3, k=1, v=2]

We generate indices using range(1, 3 + 1, 1), which gives 1, 2, 3. At each index, we multiply by v = 2:

idx	Before	Calculation	After
1	2	`(2 * 2) % mod`	4
2	9	`(9 * 2) % mod`	18
3	4	`(4 * 2) % mod`	8

Array after Query 2: [3, 4, 18, 8, 15]

Here k = 1 means we visit every index in the range [1, 3] consecutively. Also note index 2 was modified by both queries (first *3, then *2), accumulating the effects.

Final Step: Bitwise XOR of all elements

We fold xor across the final array [3, 4, 18, 8, 15]:

Step	Binary (5-bit)	Running XOR (decimal)
start with 3	`00011`	3
XOR 4	`00100`	7 (`00111`)
XOR 18	`10010`	21 (`10101`)
XOR 8	`01000`	29 (`11101`)
XOR 15	`01111`	18 (`10010`)

Answer: 18

This walkthrough demonstrates the key ideas of the approach: each query is handled independently by stepping through range(l, r + 1, k), multiple queries can compound on the same index, and once the array reaches its final state, a single XOR fold collapses everything into the result.

Solution Implementation

1from typing import List
2from functools import reduce
3from operator import xor
4
5
6class Solution:
7    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
8        # Modulus used to keep multiplication results bounded.
9        MOD = 10**9 + 7
10
11        # Process each query: it specifies a start index `left`, an end index
12        # `right`, a step `step`, and a multiplier `value`.
13        for left, right, step, value in queries:
14            # Walk from `left` to `right` (inclusive) jumping by `step`,
15            # multiplying each selected element by `value` modulo MOD.
16            for index in range(left, right + 1, step):
17                nums[index] = nums[index] * value % MOD
18
19        # Return the XOR of all elements after all queries are applied.
20        return reduce(xor, nums)
21

1class Solution {
2    public int xorAfterQueries(int[] nums, int[][] queries) {
3        // Modulus used to keep multiplication results within int range.
4        final int MOD = (int) 1e9 + 7;
5
6        // Process each query: multiply selected elements by the given value.
7        for (int[] query : queries) {
8            int left = query[0];   // Start index (inclusive).
9            int right = query[1];  // End index (inclusive).
10            int step = query[2];   // Step size between affected indices.
11            int value = query[3];  // Multiplier value.
12
13            // Multiply every element at indices left, left + step, ... up to right.
14            for (int index = left; index <= right; index += step) {
15                // Use long during multiplication to avoid integer overflow,
16                // then take the modulus before casting back to int.
17                nums[index] = (int) (1L * nums[index] * value % MOD);
18            }
19        }
20
21        // Compute the XOR of all elements after applying every query.
22        int answer = 0;
23        for (int num : nums) {
24            answer ^= num;
25        }
26
27        return answer;
28    }
29}
30

1class Solution {
2public:
3    int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
4        const int kMod = 1e9 + 7;  // Modulus for multiplication to prevent overflow
5
6        // Process each query
7        for (const auto& query : queries) {
8            int left = query[0];    // Start index of the range
9            int right = query[1];   // End index of the range
10            int step = query[2];    // Step size between affected indices
11            int multiplier = query[3];  // Value to multiply by
12
13            // Multiply selected elements (from left to right with given step) by the multiplier
14            for (int index = left; index <= right; index += step) {
15                nums[index] = 1LL * nums[index] * multiplier % kMod;
16            }
17        }
18
19        // Compute the XOR of all elements in the modified array
20        int answer = 0;
21        for (int value : nums) {
22            answer ^= value;
23        }
24
25        return answer;
26    }
27};
28

1function xorAfterQueries(nums: number[], queries: number[][]): number {
2    // Modulus value used to keep multiplication results within bounds
3    const mod = 1e9 + 7;
4
5    // Process each query: [left, right, step, value]
6    for (const [left, right, step, value] of queries) {
7        // Multiply selected elements (from left to right, stepping by `step`) by `value`
8        for (let index = left; index <= right; index += step) {
9            nums[index] = (nums[index] * value) % mod;
10        }
11    }
12
13    // Compute the XOR of all elements in the array and return it
14    return nums.reduce((accumulator, current) => accumulator ^ current, 0);
15}
16

Time and Space Complexity

Time Complexity: O(q × n/k), where n is the length of the array nums, q is the number of queries, and k is the step size in each query. For each query, the inner loop iterates over the range [l, r] with a step of k, performing at most O((r - l) / k) = O(n/k) operations. With q queries, the total time complexity is O(q × n/k). The final reduce(xor, nums) operation takes O(n) time, which is dominated by the query processing.
Space Complexity: O(1). The algorithm modifies the array nums in place and uses only a constant amount of extra space for variables such as l, r, k, v, and idx. No additional data structures proportional to the input size are allocated.

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

Common Pitfalls

Pitfall 1: Forgetting to Apply the Modulo (or Applying It Incorrectly)

The most common mistake is omitting the modulo operation, or applying it in the wrong place. Since nums[idx] is repeatedly multiplied across multiple queries, the values can grow extremely large very quickly. If you forget the modulo, you may produce results that don't match the expected answer (which is computed under 10^9 + 7).

Incorrect:

# Multiplies without bounding the value — final XOR will be wrong.
nums[index] = nums[index] * value

A subtler version of this mistake is taking the modulo only at the very end (e.g., on the XOR result) rather than after each multiplication. The XOR of the modulo-reduced values is not equal to the modulo of the XOR of the un-reduced values, so the answer will differ.

Solution: Apply % MOD immediately after every multiplication so each stored element stays in the canonical range [0, MOD):

nums[index] = nums[index] * value % MOD

Pitfall 2: Off-by-One Error on the Upper Bound

The problem states the loop runs while idx <= r_i, meaning r_i is inclusive. A natural mistake is to write range(left, right, step), which stops before right and skips the final valid index.

Incorrect:

for index in range(left, right, step):   # misses index == right
    ...

Solution: Use right + 1 as the stop value so the endpoint is included, exactly matching the while idx <= r semantics:

for index in range(left, right + 1, step):
    ...

Pitfall 3: Empty Array and `reduce` Without an Initial Value

reduce(xor, nums) raises a TypeError if nums is empty, because reduce has no value to start from. While the constraints usually guarantee n >= 1, relying on that without thought is risky if the constraints change.

Solution: Supply an explicit initializer of 0 (the identity element for XOR), which is safe for any array, including an empty one:

return reduce(xor, nums, 0)

Pitfall 4: Misjudging the Time Complexity / Attempting Premature Optimization

The simulation is O(q * n) in the worst case (k = 1). Some solvers panic and try to build a clever difference-array or segment-tree optimization. However, multiplication is not additive in a way that a standard difference array handles directly, and a step k that varies per query makes a single prefix structure awkward.

Solution: For the given constraints, the straightforward simulation is typically sufficient and is the intended approach. Don't over-engineer:

If optimization is genuinely required, consider grouping queries by step value k or using a per-step difference array on the exponents (track how many times each multiplier is applied, then exponentiate via fast power at the end). But only pursue this when the constraints clearly demand it.

The key takeaway: confirm the constraints first, then choose the simplest correct approach that fits within the time limit.

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: