Skip to content

3653. XOR After Range Multiplication Queries I

Description

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

For each query, you must apply the following operations in order:

  • Set idx = li.
  • While idx <= ri:
    • Update: nums[idx] = (nums[idx] * vi) % (109 + 7)
    • Set idx += ki.

Return the bitwise XOR of all elements in nums after processing all queries.

 

Example 1:

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

Output: 4

Explanation:

  • A single query [0, 2, 1, 4] multiplies every element from index 0 through index 2 by 4.
  • The array changes from [1, 1, 1] to [4, 4, 4].
  • The XOR of all elements is 4 ^ 4 ^ 4 = 4.

Example 2:

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

Output: 31

Explanation:

  • The first query [1, 4, 2, 3] multiplies the elements at indices 1 and 3 by 3, transforming the array to [2, 9, 1, 15, 4].
  • The second query [0, 2, 1, 2] multiplies the elements at indices 0, 1, and 2 by 2, resulting in [4, 18, 2, 15, 4].
  • Finally, the XOR of all elements is 4 ^ 18 ^ 2 ^ 15 ^ 4 = 31.​​​​​​​​​​​​​​

 

Constraints:

  • 1 <= n == nums.length <= 103
  • 1 <= nums[i] <= 109
  • 1 <= q == queries.length <= 103
  • queries[i] = [li, ri, ki, vi]
  • 0 <= li <= ri < n
  • 1 <= ki <= n
  • 1 <= vi <= 105

Solutions

Solution 1: Simulation

We can directly simulate the operations described in the problem by iterating through each query and updating the corresponding elements in the array \(\textit{nums}\). Finally, we calculate the bitwise XOR of all elements in the array and return the result.

The time complexity is \(O(q \times \frac{n}{k})\), where \(n\) is the length of the array \(\textit{nums}\) and \(q\) is the number of queries. The space complexity is \(O(1)\).

1
2
3
4
5
6
7
class Solution:
    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
        mod = 10**9 + 7
        for l, r, k, v in queries:
            for idx in range(l, r + 1, k):
                nums[idx] = nums[idx] * v % mod
        return reduce(xor, nums)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int xorAfterQueries(int[] nums, int[][] queries) {
        final int mod = (int) 1e9 + 7;
        for (var q : queries) {
            int l = q[0], r = q[1], k = q[2], v = q[3];
            for (int idx = l; idx <= r; idx += k) {
                nums[idx] = (int) (1L * nums[idx] * v % mod);
            }
        }
        int ans = 0;
        for (int x : nums) {
            ans ^= x;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        const int mod = 1e9 + 7;
        for (const auto& q : queries) {
            int l = q[0], r = q[1], k = q[2], v = q[3];
            for (int idx = l; idx <= r; idx += k) {
                nums[idx] = 1LL * nums[idx] * v % mod;
            }
        }
        int ans = 0;
        for (int x : nums) {
            ans ^= x;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func xorAfterQueries(nums []int, queries [][]int) int {
    const mod = int(1e9 + 7)
    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] = nums[idx] * v % mod
        }
    }
    ans := 0
    for _, x := range nums {
        ans ^= x
    }
    return ans
}

1
2
3
4
5
6
7
8
9
function xorAfterQueries(nums: number[], queries: number[][]): number {
    const mod = 1e9 + 7;
    for (const [l, r, k, v] of queries) {
        for (let idx = l; idx <= r; idx += k) {
            nums[idx] = (nums[idx] * v) % mod;
        }
    }
    return nums.reduce((acc, x) => acc ^ x, 0);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
impl Solution {
    pub fn xor_after_queries(mut nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {
        let modv: i64 = 1_000_000_007;
        for q in queries {
            let (l, r, k, v) = (q[0] as usize, q[1] as usize, q[2] as usize, q[3] as i64);
            let mut idx = l;
            while idx <= r {
                nums[idx] = ((nums[idx] as i64 * v) % modv) as i32;
                idx += k;
            }
        }
        let mut ans = 0;
        for x in nums {
            ans ^= x;
        }
        return ans;
    }
}

Comments