XOR After Range Multiplication Queries I

Problem summary

We are given an array nums and a list of queries.

Each query is [li, ri, ki, vi], and we must:

• start at index li
• keep jumping by ki
• stop once we pass ri
• multiply every visited element by vi
• take modulo 10^9 + 7 after each update

After processing all queries, we return the XOR of the final array.

Intuition

This problem looks fancy because of the jump pattern, but the constraints are small:

• n <= 1000
• q <= 1000

That means we do not need a heavy data structure.

We can simply simulate every query exactly as described.

For one query:

1. set index = li
2. while index <= ri, update nums[index]
3. move to index += ki

Once all queries are done, make one final pass and XOR every number together.

Why simulation is enough

In the worst case, each query may touch O(n) positions.

If we do that for all q queries, the total work is:

O(n * q)

With both values capped at 1000, this is completely fine.

Algorithm

For every query [li, ri, ki, vi]:

1. iterate index from li to ri with step ki
2. update:

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

After all queries:

1. initialize answer = 0
2. XOR every element of nums into answer
3. return answer

class Solution {
    private static final int MOD = 1_000_000_007;

    public int xorAfterQueries(int[] nums, int[][] queries) {
        for (int[] query : queries) {
            int left = query[0];
            int right = query[1];
            int step = query[2];
            int value = query[3];

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

        int answer = 0;
        for (int num : nums) {
            answer ^= num;
        }

        return answer;
    }
}

Walkthrough

Take:

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

Query 1: [1, 4, 2, 3]

Start at index 1, then jump by 2.

Visited indices are:

• 1
• 3

So the array becomes:

[2, 9, 1, 15, 4]

Query 2: [0, 2, 1, 2]

Start at index 0, then jump by 1.

Visited indices are:

• 0
• 1
• 2

So the array becomes:

[4, 18, 2, 15, 4]

Now compute XOR:

4 ^ 18 ^ 2 ^ 15 ^ 4 = 31

So the answer is 31.

Complexity analysis

Time Complexity: O(n * q)

• each query may touch up to O(n) indices
• after that, one extra O(n) pass computes the XOR

Space Complexity: O(1)

We only update the input array and use a few variables.

Common mistakes

1. Forgetting the modulo during updates

The multiplication should be reduced by 10^9 + 7 every time, not only at the end.

2. Using int * int directly in languages with overflow

Before taking modulo, the product can be larger than a 32-bit integer, so use a wider type like long, long long, or int64.

3. XORing before all queries finish

The XOR is computed only after every query has already updated the array.