LeetCode Problem 3653

Difficulty: 🟡 Medium
Topics: Array, Divide and Conquer, Simulation

Solution

LeetCode 3653 - XOR After Range Multiplication Queries I

Problem Understanding

We are given an integer array nums and a list of queries. Each query has the form:

[li, ri, ki, vi]

For a query, we start at index li and repeatedly move forward by ki positions until we exceed ri.

Every visited index is updated as:

nums[idx] = (nums[idx] * vi) % (10^9 + 7)

All queries are processed sequentially, meaning the result of one query becomes the starting state for the next query.

After every query has been applied, we must compute and return the bitwise XOR of all elements in the final array.

In other words, the task is simply to simulate the updates exactly as described and then XOR together all final values.

The constraints are:

• n <= 1000
• q <= 1000
• nums[i] <= 10^9
• vi <= 10^5

These constraints are relatively small. Even if every query touches nearly every element, the total amount of work remains manageable.

The important observation is that the problem statement explicitly defines the indices that must be updated. There is no hidden optimization requirement, and the maximum input size is only one thousand elements and one thousand queries.

Some important edge cases include:

• ki = 1, which means every index in the interval [li, ri] is updated.
• li = ri, where only a single element is modified.
• ki > (ri - li), where only the starting index is updated.
• Multiple queries affecting the same index repeatedly.
• Large multiplication values that require modulo reduction after every update.

The problem guarantees that all indices generated by the process are valid and that every query satisfies 0 <= li <= ri < n.

Approaches

Brute Force Approach

The most direct approach is to follow the statement literally.

For each query:

1. Start at index li.
2. While the current index is at most ri:

• Multiply the element by vi.
• Apply modulo 10^9 + 7.
• Advance by ki.

After all queries are processed, iterate through the array and compute the XOR of every value.

This approach is correct because it performs exactly the operations described in the problem statement.

Since each query can visit at most n positions and there are at most q queries, the worst case is:

O(n * q)

With n, q <= 1000, this is only about one million updates, which is easily fast enough.

Optimal Approach

Because the constraints are small, the brute-force simulation is already optimal for the given problem.

There is no need for advanced data structures such as segment trees, difference arrays, or lazy propagation. The update pattern depends on arbitrary arithmetic progressions defined by (li, ki), making such structures unnecessary and potentially more complicated than the straightforward solution.

The best solution is therefore the direct simulation described above.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(q · n)	O(1)	Simulate every affected index directly
Optimal	O(q · n)	O(1)	Same approach, constraints are small enough that direct simulation is optimal

Algorithm Walkthrough

1. Define the modulo constant:

MOD = 1,000,000,007

Every multiplication result must be reduced modulo this value. 2. Process each query one at a time.

For a query [l, r, k, v], initialize:

idx = l

3. Repeatedly update the current position while idx <= r.

For every visited index:

nums[idx] = (nums[idx] * v) % MOD

Then move to the next valid position:

idx += k

4. Continue until all queries have been processed.

At this point, nums contains the final state of the array. 5. Compute the XOR of all elements.

Initialize:

answer = 0

Then iterate through the array:

answer ^= value

6. Return the final XOR value.

Why it works

The algorithm exactly follows the definition of every query. For each query, it visits precisely the indices generated by the sequence:

li, li + ki, li + 2ki, ...

while remaining within ri.

Every update is applied in the same order required by the problem statement, and the final XOR is computed from the resulting array. Since the algorithm performs exactly the specified operations, it always produces the correct answer.

Problem Understanding

We are given an array nums and a list of queries. Each query has the form [li, ri, ki, vi].

For a single query, we start at index li and repeatedly jump forward by ki until we pass ri. Every visited position is multiplied by vi, and the result is reduced modulo 10^9 + 7.

Formally, the query affects the indices

$$li,; li + ki,; li + 2ki,; \dots$$

as long as the index remains at most ri.

All queries are processed sequentially, meaning later queries see the modifications made by earlier queries.

After every query has been applied, we compute the bitwise XOR of all elements of the final array and return that value.

The constraints are relatively small:

• n <= 1000
• q <= 1000
• ki >= 1

The maximum number of positions touched by a query is at most n. Therefore, even a direct simulation remains practical.

Important edge cases include:

• ki = 1, which means every index in [li, ri] is updated.
• li = ri, where exactly one element is modified.
• Multiple queries affecting the same index, requiring repeated modular multiplications.
• vi = 1, which leaves affected elements unchanged.
• Large intermediate values, which must always be reduced modulo 10^9 + 7.

Approaches

Brute Force

The most direct approach is to simulate the process exactly as described.

For every query:

1. Start at idx = li.
2. While idx <= ri:

• Update nums[idx].
• Increase idx by ki.

After all queries are processed, compute the XOR of every element in the array.

This approach is correct because it follows the problem statement literally.

Since each query touches at most n positions and both n and q are at most 1000, the worst-case number of updates is at most:

$$1000 \times 1000 = 10^6$$

which is easily manageable.

Key Observation

A more sophisticated data structure is unnecessary.

The constraints are intentionally small. Even when every query has ki = 1, there are only one million update operations in total. Therefore, the straightforward simulation already runs comfortably within typical time limits.

As a result, the optimal solution is simply the direct simulation.

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(q·n)	O(1)	Directly simulate every affected index
Optimal	O(q·n)	O(1)	Same approach, constraints are small enough that simulation is optimal

Algorithm Walkthrough

1. Define the modulus MOD = 10^9 + 7.
2. Process each query [l, r, k, v] in the given order.
3. Initialize idx = l.
4. While idx <= r, update the corresponding element:

$$nums[idx] = (nums[idx] \times v) \bmod MOD$$

Then advance:

$$idx = idx + k$$ 5. After all queries have been processed, compute the XOR of every element in the final array. 6. Return the resulting XOR value.

Why it works

The algorithm exactly implements the update rule specified in the problem statement. For every query, it visits precisely the indices

$$l,; l+k,; l+2k,; \dots$$

up to r, and applies the required modular multiplication. Since queries are processed sequentially, every update is applied in the correct order. After all updates have been completed, taking the XOR of the final array produces exactly the value requested by the problem.

Python Solution

from typing import List

class Solution:
    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
        MOD = 1_000_000_007

        for left, right, step, value in queries:
            idx = left

            while idx <= right:
                nums[idx] = (nums[idx] * value) % MOD
                idx += step

        result = 0

        for num in nums:
            result ^= num

        return result

The implementation begins by defining the modulo constant required by the problem.

For each query, the code starts at left and repeatedly jumps by step. Every visited element is multiplied by the query value and immediately reduced modulo 10^9 + 7.

After all queries have been applied, the code performs a single pass through the array and accumulates the XOR of all values.

No auxiliary data structures are needed because the updates can be performed directly in the original array. MOD = 10**9 + 7

    for l, r, k, v in queries:
        idx = l
        while idx <= r:
            nums[idx] = (nums[idx] * v) % MOD
            idx += k

    xor_value = 0
    for num in nums:
        xor_value ^= num

    return xor_value

The implementation follows the algorithm directly.

The outer loop processes queries one by one. For each query, a `while` loop walks through exactly the indices defined by the arithmetic progression starting at `l` with step size `k`. Every visited element is multiplied by `v` and reduced modulo `10^9 + 7`.

After all updates have been applied, a final pass computes the XOR of every array element and returns the result.

## Go Solution

```go
func xorAfterQueries(nums []int, queries [][]int) int {
	const MOD = 1000000007

	for _, query := range queries {
		left := query[0]
		right := query[1]
		step := query[2]
		value := query[3]

		for idx := left; idx <= right; idx += step {
			nums[idx] = int((int64(nums[idx]) * int64(value)) % MOD)
		}
	}

	result := 0

	for _, num := range nums {
		result ^= num
	}

	return result
}

The Go solution follows the same logic as the Python version.

One important difference is that multiplication is performed using int64 before taking the modulo. This prevents overflow on platforms where int may not safely hold the intermediate product. After the modulo operation, the result is converted back to int.

The rest of the implementation is identical: simulate all updates, then compute the final XOR. for _, q := range queries { l, r, k, v := q[0], q[1], q[2], q[3]

	for idx := l; idx <= r; idx += k {
		nums[idx] = int((int64(nums[idx]) * int64(v)) % MOD)
	}
}

xorValue := 0
for _, num := range nums {
	xorValue ^= num
}

return xorValue

}

The Go implementation is structurally identical to the Python version.

The main difference is that multiplication is performed using `int64` before applying the modulus. This prevents overflow on platforms where `int` is 32-bit. After the modular reduction, the value is safely converted back to `int`.

## Worked Examples

### Example 1

**Input**

nums = [1,1,1] queries = [[0,2,1,4]] nums = [1, 1, 1] queries = [[0, 2, 1, 4]]

Initial array:

| Index | Value |
| --- | --- |
| 0 | 1 |
| 1 | 1 |
| 2 | 1 |

Query:

[0,2,1,4]

| idx | Update | Array State |
| --- | --- | --- |
| 0 | 1 × 4 = 4 | [4,1,1] |
| 1 | 1 × 4 = 4 | [4,4,1] |
| 2 | 1 × 4 = 4 | [4,4,4] |

Final XOR:

4 ^ 4 ^ 4 = 4 Processing query [0, 2, 1, 4]:

idx	Update
0	1 × 4 = 4
1	1 × 4 = 4
2	1 × 4 = 4

Final array:

[4, 4, 4]

XOR computation:

4 ^ 4 ^ 4
= 0 ^ 4
= 4

Answer:

4

Example 2

Input

nums = [2,3,1,5,4]
queries = [
    [1,4,2,3],
    [0,2,1,2]
nums = [2, 3, 1, 5, 4]
queries = [
    [1, 4, 2, 3],
    [0, 2, 1, 2]
]

Initial array:

[2,3,1,5,4]

First query:

[1,4,2,3]

Affected indices:

1, 3

idx	Update	Array State
1	3 × 3 = 9	[2,9,1,5,4]
3	5 × 3 = 15	[2,9,1,15,4]

Array after first query:

[2,9,1,15,4]

Second query:

[0,2,1,2]

Affected indices:

0,1,2

idx	Update	Array State
0	2 × 2 = 4	[4,9,1,15,4]
1	9 × 2 = 18	[4,18,1,15,4]
2	1 × 2 = 2	[4,18,2,15,4]
[2, 3, 1, 5, 4]

Processing query `[1, 4, 2, 3]`:

Affected indices: `1, 3`

| Index | Old | New |
| --- | --- | --- |
| 1 | 3 | 9 |
| 3 | 5 | 15 |

Array becomes:

[2, 9, 1, 15, 4]

Processing query `[0, 2, 1, 2]`:

Affected indices: `0, 1, 2`

| Index | Old | New |
| --- | --- | --- |
| 0 | 2 | 4 |
| 1 | 9 | 18 |
| 2 | 1 | 2 |

Final array:

[4,18,2,15,4]

Final XOR:

4 ^ 18 ^ 2 ^ 15 ^ 4 = 31 [4, 18, 2, 15, 4]

XOR computation:

4 ^ 18 = 22 22 ^ 2 = 20 20 ^ 15 = 27 27 ^ 4 = 31

Answer:

31

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(q · n) | Each query can visit at most n positions |
| Space | O(1) | Updates are performed in place |

In the worst case, every query has `ki = 1` and spans the entire array. Then each query touches `n` elements, producing `q * n` total updates. With `n, q <= 1000`, this is at most one million operations, which is easily within limits. The algorithm uses only a few variables beyond the input array, so the extra space usage is constant.

## Test Cases

```python
from typing import List

s = Solution()

assert s.xorAfterQueries([1, 1, 1], [[0, 2, 1, 4]]) == 4  # example 1

assert s.xorAfterQueries(
    [2, 3, 1, 5, 4],
    [[1, 4, 2, 3], [0, 2, 1, 2]]
) == 31  # example 2

assert s.xorAfterQueries([7], []) == 7  # single element, no queries

assert s.xorAfterQueries([5], [[0, 0, 1, 3]]) == 15  # single element updated

assert s.xorAfterQueries([1, 2, 3, 4], [[0, 3, 5, 10]]) == (10 ^ 2 ^ 3 ^ 4)  # step larger than interval

assert s.xorAfterQueries([1, 1, 1, 1], [[0, 3, 2, 2]]) == (2 ^ 1 ^ 2 ^ 1)  # alternating indices

assert s.xorAfterQueries(
    [2, 2],
    [[0, 1, 1, 2], [0, 1, 1, 3]]
) == (12 ^ 12)  # repeated updates

assert s.xorAfterQueries(
    [1_000_000_000],
    [[0, 0, 1, 100_000]]
) == ((1_000_000_000 * 100_000) % 1_000_000_007)  # large multiplication

assert s.xorAfterQueries(
    [1, 2, 3, 4, 5],
    [[0, 4, 1, 1]]
) == (1 ^ 2 ^ 3 ^ 4 ^ 5)  # multiplying by one changes nothing

Test Summary

Test	Why
Example 1	Verifies basic full-range update
Example 2	Verifies multiple sequential queries
Single element, no queries	Checks minimal array behavior
Single element updated	Verifies smallest valid update
Step larger than interval	Ensures only starting index is modified
Alternating indices	Tests arithmetic progression updates
Repeated updates	Verifies cumulative multiplication effects
Large multiplication	Confirms modulo handling
Multiply by one	Confirms unchanged values are handled correctly

Edge Cases

Step Size Larger Than the Range

Consider a query where ki is larger than ri - li. In this situation, only the starting index is visited before the next jump exceeds the range. An implementation that incorrectly assumes multiple updates may produce wrong results. The loop condition idx <= right naturally handles this case and updates exactly one element.

Single Element Interval

When li == ri, the query targets exactly one index. This is a common source of off-by-one errors if loops are written incorrectly. Because the implementation starts at li and checks idx <= right, the single index is updated exactly once.

Multiple Queries Affecting the Same Position

An index may be updated by many different queries. The problem requires that queries be processed sequentially, with each query operating on the current state of the array. The implementation modifies the array in place, ensuring that every later query sees the results of all earlier updates.

Large Intermediate Products

Values can become very large after repeated multiplications. Without applying modulo reduction after each update, integer values could grow unnecessarily large and potentially overflow in some languages. The implementation performs:

(nums[idx] * value) % (10^9 + 7)

immediately after every multiplication, exactly as required by the problem statement. | Time | O(q·n) | Each query can touch at most n indices | | Space | O(1) | Updates are performed in place |

In the worst case, every query has ki = 1, causing it to visit all n positions. Therefore the total work is bounded by q × n. With n, q ≤ 1000, this is at most one million updates, which is easily feasible. No auxiliary data structures proportional to input size are required.

Test Cases

sol = Solution()

# Example 1
assert sol.xorAfterQueries([1, 1, 1], [[0, 2, 1, 4]]) == 4

# Example 2
assert sol.xorAfterQueries(
    [2, 3, 1, 5, 4],
    [[1, 4, 2, 3], [0, 2, 1, 2]]
) == 31

# Single element array
assert sol.xorAfterQueries([7], [[0, 0, 1, 5]]) == 35

# Multiplier of 1 changes nothing
assert sol.xorAfterQueries([1, 2, 3], [[0, 2, 1, 1]]) == (1 ^ 2 ^ 3)

# Step size larger than range length
assert sol.xorAfterQueries([2, 4, 6], [[0, 2, 3, 10]]) == (20 ^ 4 ^ 6)

# Multiple updates on same position
assert sol.xorAfterQueries([2], [[0, 0, 1, 3], [0, 0, 1, 5]]) == 30

# Only every second index affected
assert sol.xorAfterQueries(
    [1, 1, 1, 1, 1],
    [[0, 4, 2, 2]]
) == (2 ^ 1 ^ 2 ^ 1 ^ 2)

# Large value requiring modulo
MOD = 10**9 + 7
assert sol.xorAfterQueries(
    [10**9],
    [[0, 0, 1, 10**5]]
) == ((10**9 * 10**5) % MOD)

# No overlapping updates
assert sol.xorAfterQueries(
    [1, 2, 3, 4],
    [[0, 0, 1, 2], [3, 3, 1, 3]]
) == (2 ^ 2 ^ 3 ^ 12)

# Full range updated repeatedly
assert sol.xorAfterQueries(
    [1, 1, 1],
    [[0, 2, 1, 2], [0, 2, 1, 3]]
) == (6 ^ 6 ^ 6)

Test	Why
Example 1	Verifies basic full-range update
Example 2	Verifies multiple queries and overlapping effects
Single element array	Smallest valid array
Multiplier equals 1	Confirms no-op updates
Large step size	Ensures arithmetic progression handling
Multiple updates on same position	Verifies sequential application
Every second index	Tests sparse updates
Large value with modulo	Confirms modular arithmetic
Non-overlapping updates	Verifies independent updates
Repeated full-range updates	Tests cumulative multiplication

Edge Cases

Single-Element Array

When n = 1, every valid query must target index 0. Implementations sometimes incorrectly assume multiple indices exist or mishandle loop boundaries. The solution handles this naturally because the update loop operates correctly even when the range contains only one element.

Step Size Larger Than the Range

Consider a query such as [0, 2, 3, 10]. The progression contains only index 0, because the next index would be 3, which exceeds r. A buggy implementation might accidentally update extra positions. The while idx <= r condition guarantees that only valid progression elements are modified.

Repeated Updates on the Same Index

An index may be affected by many different queries. Since queries must be processed in order, the result depends on the cumulative product of all applicable multipliers modulo 10^9 + 7. The implementation updates the array in place after every query, ensuring later queries operate on the already-modified values.

Large Intermediate Products

Values can become very large after repeated multiplications. Without modular reduction after every update, integer growth could become problematic. The implementation applies

$$(nums[idx] \times v) \bmod (10^9+7)$$

immediately after each multiplication, exactly matching the problem specification and preventing overflow issues.