XOR After Range Multiplication Queries I solution and explanation
Infosys
9 more videos on this problem
XOR After Range Multiplication Queries I | Simple Explanation | Leetcode 3653 | codestorywithMIKcodestorywithMIK · 8:27 · 5K views
3653. XOR After Range Multiplication Queries I | Leetcode Daily - PythonLeetcode Daily · 5:58 · 306 views
LeetCode | Solved in 5:26 mins | EP65 | 3653. XOR After Range Multiplication Queries IEduardo Nakanishi · 5:26 · 234 views
XOR After Range Multiplication Queries I - Leetcode 3653 | Java | HindiKernel Queen 👑 · 3:21 · 209 views
XOR After Range Multiplication Queries I | LeetCode 3653 - Pythonimpoldev · 4:47 · 178 views
Daily Leetcode #2199: Apr 08, 2026 - 3653. XOR After Range Multiplication Queries IProgramming Live with Larry · 8:31 · 175 views
3653. XOR After Range Multiplication Queries I (Leetcode Medium)Programming Live with Larry · 4:08 · 170 views
3653. XOR After Range Multiplication Queries I | Leetcode Weekly Contest 463Break and Build · 9:26 · 105 views
Leetcode || 3653. XOR After Range Multiplication Queries I || ArrayKomal Pal · 18:12 · 94 views
XOR After Range Multiplication Queries I | LeetCode 3653 | Java Code | Developer CoderDeveloper Coder · 10:10 · 74 views
The problem
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.
- Update:
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 <= 1031 <= nums[i] <= 1091 <= q == queries.length <= 103queries[i] = [li, ri, ki, vi]0 <= li <= ri < n1 <= ki <= n1 <= vi <= 105
Approach overview
Problem Overview: You are given an array and a list of queries. Each query multiplies every element in a subarray [l, r] by a value. After applying the operations, compute the XOR of the resulting array. The main challenge is handling repeated range updates while keeping the final XOR correct.
Approach 1: Direct Simulation (O(n * q) time, O(1) space)
The most straightforward strategy is to simulate every query exactly as described. For each query, iterate from l to r and multiply the element by the given value. After processing all queries, iterate once through the array and compute the XOR of all elements. This approach uses plain array traversal and mirrors the problem statement directly, which makes it easy to implement and debug.
The key observation is that multiplication changes multiple bits in unpredictable ways, so maintaining a running XOR during updates becomes tricky. Instead of attempting clever bit manipulations, simply update the array values and compute the XOR at the end. For typical constraints in this problem, the straightforward simulation is efficient enough.
Approach 2: Incremental XOR Update (O(n * q) time, O(1) space)
A small optimization is to maintain the global XOR while applying updates. When an element a[i] changes, remove its previous contribution from the XOR using xor ^= oldValue, update the element with the multiplication, then add the new value back using xor ^= newValue. This avoids recomputing the XOR over the entire array at the end.
The update loop for each query still iterates from l to r, so the overall complexity remains the same. However, the final XOR is always available without an additional pass. This pattern often appears in problems combining range updates with XOR aggregation and simple simulation.
Recommended for interviews: Start with the direct simulation approach. It demonstrates that you understand the mechanics of the queries and how XOR aggregation works. If the interviewer asks for improvements, explain how maintaining the XOR incrementally avoids an extra pass. Problems tagged with divide and conquer sometimes admit segment-tree optimizations, but for this version the straightforward simulation is usually expected.
Solution
We can directly simulate the operations described in the problem by iterating through each query and updating the corresponding elements in the array 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 nums and q is the number of queries. The space complexity is O(1).
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)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;
}
}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;
}
};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);
}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
}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;
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation | O(n * q) | O(1) | Best when constraints are small or moderate and implementation speed matters |
| Simulation with Incremental XOR Maintenance | O(n * q) | O(1) | Useful when you want the XOR updated during each modification without an additional array pass |
| Segment Tree / Divide and Conquer Idea | O((n + q) log n) | O(n) | Consider when constraints are very large and frequent range updates require structured queries |
Frequently asked questions
Is XOR After Range Multiplication Queries I easy or hard?
The problem is rated Medium because it combines range updates with bitwise XOR aggregation. The implementation itself is straightforward, but understanding how updates affect the XOR and reasoning about complexity requires solid array manipulation skills.
XOR After Range Multiplication Queries I Python/Java solution
A typical Python or Java solution loops through each query, multiplies elements between l and r, and finally computes the XOR of the array. The implementation is straightforward and runs in O(n * q) time with constant extra space.
How to solve XOR After Range Multiplication Queries I in O(n)?
Pure O(n) time is generally not achievable if each query modifies multiple elements. Every range multiplication potentially touches many indices, so the total work becomes proportional to the number of updated elements. The practical solution uses simulation with O(n * q) complexity.
What is the best approach for XOR After Range Multiplication Queries I?
The most practical approach is direct simulation. Apply each query by multiplying elements in the range [l, r], then compute the XOR of the array. This runs in O(n * q) time and O(1) extra space and is typically sufficient for the constraints of this problem.
Is XOR After Range Multiplication Queries I asked at Google/Amazon/Meta?
Problems involving XOR aggregation and range updates appear frequently in coding interviews at large tech companies. Variants using arrays, prefix XOR, or segment trees are commonly seen in Google, Amazon, and Meta interview preparation sets.
What data structure is used in XOR After Range Multiplication Queries I?
The standard solution relies on a simple array and simulation of updates. More advanced variations could use segment trees or divide-and-conquer structures to handle range updates and XOR queries efficiently when constraints are very large.
What is the time complexity of XOR After Range Multiplication Queries I?
The common solution runs in O(n * q) time, where n is the array size and q is the number of queries. Each query iterates through its range to update values. The space complexity is O(1) because updates are done in place.