3653. XOR After Range Multiplication Queries I

Array
Bit Manipulation
Simulation

TIME

O(q × n)

SPACE

O(1)

Intuition

With small constraints (n, q ≤ 10³), direct simulation is efficient enough. Process each query by iterating with step k and apply XOR at the end.

Solution

Step 1: Process Each Query

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

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

Step 2: Compute XOR

After all queries, XOR all elements:

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

Why Modulo?

Values can grow large after multiple multiplications. Using 10^9 + 7 keeps values bounded while preserving the multiplication result for XOR.

Complexity

Time: O(q × n/k) ≈ O(q × n) in worst case = O(10⁶)
Space: O(1) extra space

Edge Cases

Single element array
k = n (only one element updated per query)
k = 1 (all elements in range updated)
Multiple queries affecting same indices

Code

from typing import List


class Solution:
    def xorAfterMultiplication(self, nums: List[int], queries: List[List[int]]) -> int:
        """
        3653. XOR After Range Multiplication Queries I
        Time: O(q × n)
        Space: O(1)
        """
        MOD = 10**9 + 7

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

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

        return result

/**
 * 3653. XOR After Range Multiplication Queries I
 * Time: O(q × n)
 * Space: O(1)
 */
class Solution {
    public int xorAfterMultiplication(int[] nums, int[][] queries) {
        long MOD = 1_000_000_007L;

        for (int[] q : queries) {
            int l = q[0], r = q[1], k = q[2], v = q[3];

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

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

        return result;
    }
}