LeetCode 3655 | XOR After Range Multiplication Queries II | Java | Hard | CodeByTushu
Description: 🚀 Welcome Back to CodeByTushu!
In today’s video, we solve LeetCode 3655 — XOR After Range Multiplication Queries II using Square Root Decomposition and Multiplicative Difference Arrays in Java.
We are given an array and multiple queries. Each query provides a range from l to r, a step size k, and a multiplier v. We multiply elements at indices l, l+k, l+2k, and so on, using modulo 10^9 + 7.
A naive approach can require up to 10 billion operations, resulting in Time Limit Exceeded. To optimize this, we combine updates before calculating the final bitwise XOR.
We use Square Root Decomposition with a threshold B close to sqrt(n), approximately 316 for the maximum constraints.
For large step sizes, where k is at least B, we process each query directly because it touches at most around sqrt(n) elements.
For small step sizes, we group queries by k and use Multiplicative Difference Arrays. Modular inverses calculated using Fermat's Little Theorem help manage multiplication updates. Prefix products along each stride apply the grouped updates efficiently.
This approach achieves O((n + q) * sqrt(n) + q * log(MOD)) time complexity.
🔥 Problem Highlights
✅ Square Root Decomposition: Separates large and small step sizes using a sqrt(n) threshold
✅ Bounded Simulation: Processes large-step queries in at most around sqrt(n) operations each
✅ Multiplicative Difference Array: Handles grouped range multiplication updates efficiently
✅ Fermat's Little Theorem: Calculates modular inverses using MOD minus 2 as the exponent
✅ Stride Prefix Products: Applies grouped updates through prefix product sweeps
✅ Performance Optimization: Avoids billions of unnecessary operations
⏱️ TIMESTAMPS
00:00 Intro & Daily Challenge Kickoff (Streak 98 Days)
01:31 Problem Understanding & 10^10 TLE Scale Warning
03:27 Key Insights: Sqrt Decomposition & Multiplicative Diff Arrays
05:40 Optimal Sqrt Threshold & Stride-k Prefix Product
07:42 Clean Java Solution Walkthrough Line by Line
09:18 Test Cases Dry Run & Benchmark Verification (148 ms, Beats 98.6%)
11:45 Time Complexity Analysis (O((N + Q) * sqrt(N)) Time)
13:05 Space Complexity Analysis (O(N + Q) Auxiliary Space)
13:59 Day 9 Wrap-up & Channel Resources
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/April/09-April/3655-XOR-After-Range-Multiplication-Queries-II
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/April/09-April/3655-XOR-After-Range-Multiplication-Queries-II/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/April/09-April/3655-XOR-After-Range-Multiplication-Queries-II/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/April/09-April/3655-XOR-After-Range-Multiplication-Queries-II/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/April/09-April/3655-XOR-After-Range-Multiplication-Queries-II/solution.js
🔗 LeetCode Source Code
📌 Admin type the link
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions and daily questions.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Hard Problems
Java DSA Preparation
Square Root Decomposition
Multiplicative Difference Arrays
Modular Arithmetic & Number Theory
Bit Manipulation
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why do we use the square root threshold B = sqrt(n) to divide the queries?
1️⃣ Because queries with k at least sqrt(n) touch at most around sqrt(n) elements, balancing both processing strategies
2️⃣ Because square root is required by Fermat's Little Theorem to compute modular inverses
3️⃣ Because bitwise XOR can only be computed in blocks of size sqrt(n)
4️⃣ Because modulo 10^9 + 7 only supports arrays of size up to sqrt(n)
#LeetCode3655 #LeetCode #XORAfterRangeMultiplicationQueriesII #Java #JavaDSA #SquareRootDecomposition #DifferenceArray #BitManipulation #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
In today’s video, we solve LeetCode 3655 — XOR After Range Multiplication Queries II using Square Root Decomposition and Multiplicative Difference Arrays in Java.
We are given an array and multiple queries. Each query provides a range from l to r, a step size k, and a multiplier v. We multiply elements at indices l, l+k, l+2k, and so on, using modulo 10^9 + 7.
A naive approach can require up to 10 billion operations, resulting in Time Limit Exceeded. To optimize this, we combine updates before calculating the final bitwise XOR.
We use Square Root Decomposition with a threshold B close to sqrt(n), approximately 316 for the maximum constraints.
For large step sizes, where k is at least B, we process each query directly because it touches at most around sqrt(n) elements.
For small step sizes, we group queries by k and use Multiplicative Difference Arrays. Modular inverses calculated using Fermat's Little Theorem help manage multiplication updates. Prefix products along each stride apply the grouped updates efficiently.
This approach achieves O((n + q) * sqrt(n) + q * log(MOD)) time complexity.
🔥 Problem Highlights
✅ Square Root Decomposition: Separates large and small step sizes using a sqrt(n) threshold
✅ Bounded Simulation: Processes large-step queries in at most around sqrt(n) operations each
✅ Multiplicative Difference Array: Handles grouped range multiplication updates efficiently
✅ Fermat's Little Theorem: Calculates modular inverses using MOD minus 2 as the exponent
✅ Stride Prefix Products: Applies grouped updates through prefix product sweeps
✅ Performance Optimization: Avoids billions of unnecessary operations
⏱️ TIMESTAMPS
00:00 Intro & Daily Challenge Kickoff (Streak 98 Days)
01:31 Problem Understanding & 10^10 TLE Scale Warning
03:27 Key Insights: Sqrt Decomposition & Multiplicative Diff Arrays
05:40 Optimal Sqrt Threshold & Stride-k Prefix Product
07:42 Clean Java Solution Walkthrough Line by Line
09:18 Test Cases Dry Run & Benchmark Verification (148 ms, Beats 98.6%)
11:45 Time Complexity Analysis (O((N + Q) * sqrt(N)) Time)
13:05 Space Complexity Analysis (O(N + Q) Auxiliary Space)
13:59 Day 9 Wrap-up & Channel Resources
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/April/09-April/3655-XOR-After-Range-Multiplication-Queries-II
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/April/09-April/3655-XOR-After-Range-Multiplication-Queries-II/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/April/09-April/3655-XOR-After-Range-Multiplication-Queries-II/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/April/09-April/3655-XOR-After-Range-Multiplication-Queries-II/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/April/09-April/3655-XOR-After-Range-Multiplication-Queries-II/solution.js
🔗 LeetCode Source Code
📌 Admin type the link
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions and daily questions.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Hard Problems
Java DSA Preparation
Square Root Decomposition
Multiplicative Difference Arrays
Modular Arithmetic & Number Theory
Bit Manipulation
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why do we use the square root threshold B = sqrt(n) to divide the queries?
1️⃣ Because queries with k at least sqrt(n) touch at most around sqrt(n) elements, balancing both processing strategies
2️⃣ Because square root is required by Fermat's Little Theorem to compute modular inverses
3️⃣ Because bitwise XOR can only be computed in blocks of size sqrt(n)
4️⃣ Because modulo 10^9 + 7 only supports arrays of size up to sqrt(n)
#LeetCode3655 #LeetCode #XORAfterRangeMultiplicationQueriesII #Java #JavaDSA #SquareRootDecomposition #DifferenceArray #BitManipulation #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
