LeetCode 3315 | Construct the Minimum Bitwise Array II | Java | Medium | Bit | CodeByTushu
Description: 🚀 Welcome Back to CodeByTushu!
In today’s video, we solve LeetCode 3315 - Construct the Minimum Bitwise Array II using Bit Manipulation in Java.
We need to construct an array ans such that for each prime number in nums, the bitwise OR of ans[i] and ans[i] + 1 equals nums[i], while minimizing ans[i]. Unlike Part I, where numbers were small enough for linear checks, here numbers can reach 10^9, meaning any linear scan or brute-force trial will lead to Time Limit Exceeded. A closed-form O(1) mathematical bitwise formulation is essential.
Crucially, the operation of taking the bitwise OR of x and x + 1 always evaluates to an odd integer because either x or x + 1 is odd. The only even prime is 2, for which no non-negative integer x exists, resulting in -1. For every odd prime, the number ends with a block of trailing 1s. Adding 1 to x flips its lowest 0-bit to 1 and resets lower bits to 0. To achieve the absolute minimum x, we must clear the highest bit within the contiguous trailing 1s of nums[i]. By isolating the lowest set bit of nums[i] + 1 and shifting it right by one, we obtain this exact bit in O(1) time, yielding optimal O(n) runtime and O(1) auxiliary space.
🔥 Problem Highlights
✅ Overcomes large input values up to 10^9 where brute-force linear search fails
✅ Parity invariant analysis: the bitwise OR of x and x + 1 is always odd for non-negative integers
✅ Immediate edge case detection: even prime 2 maps to -1
✅ Precise bitwise transition analysis under addition of 1
✅ O(1) closed-form formula using the lowest set bit of nums[i] + 1, shifted right by one
✅ Optimal O(n) time and O(1) auxiliary space complexity
⏱️ TIMESTAMPS
00:00 Intro
01:08 Problem Understanding and Constraints
02:34 Core Observations and Mathematical Insight
03:36 Algorithmic Approach and Bit Manipulation Strategy
04:39 Line-by-Line Java Code Walkthrough
05:51 Step-by-Step Test Run and Dry Run
07:30 Time Complexity Analysis
08:13 Space Complexity Analysis
08:50 Outro and Key Takeaways
📂 Problem Folder and Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/January/21-January/3315-Construct-the-Minimum-Bitwise-Array-II
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/21-January/3315-Construct-the-Minimum-Bitwise-Array-II/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/21-January/3315-Construct-the-Minimum-Bitwise-Array-II/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/21-January/3315-Construct-the-Minimum-Bitwise-Array-II/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/21-January/3315-Construct-the-Minimum-Bitwise-Array-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, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Medium Problems
Java DSA Preparation
Bit Manipulation
Binary Invariants
Lowbit Arithmetic Tricks
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 does clearing the highest bit among the trailing 1s of nums[i] minimize the value of ans[i]?
1️⃣ Higher bit positions correspond to larger powers of 2, so subtracting them reduces the number the most
2️⃣ Clearing lower bits creates negative numbers
3️⃣ Higher bits are always 0 in prime numbers
4️⃣ It prevents integer overflow in 32-bit registers
#LeetCode3315 #LeetCode #ConstructTheMinimumBitwiseArrayII #Java #JavaDSA #BitManipulation #Array #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
In today’s video, we solve LeetCode 3315 - Construct the Minimum Bitwise Array II using Bit Manipulation in Java.
We need to construct an array ans such that for each prime number in nums, the bitwise OR of ans[i] and ans[i] + 1 equals nums[i], while minimizing ans[i]. Unlike Part I, where numbers were small enough for linear checks, here numbers can reach 10^9, meaning any linear scan or brute-force trial will lead to Time Limit Exceeded. A closed-form O(1) mathematical bitwise formulation is essential.
Crucially, the operation of taking the bitwise OR of x and x + 1 always evaluates to an odd integer because either x or x + 1 is odd. The only even prime is 2, for which no non-negative integer x exists, resulting in -1. For every odd prime, the number ends with a block of trailing 1s. Adding 1 to x flips its lowest 0-bit to 1 and resets lower bits to 0. To achieve the absolute minimum x, we must clear the highest bit within the contiguous trailing 1s of nums[i]. By isolating the lowest set bit of nums[i] + 1 and shifting it right by one, we obtain this exact bit in O(1) time, yielding optimal O(n) runtime and O(1) auxiliary space.
🔥 Problem Highlights
✅ Overcomes large input values up to 10^9 where brute-force linear search fails
✅ Parity invariant analysis: the bitwise OR of x and x + 1 is always odd for non-negative integers
✅ Immediate edge case detection: even prime 2 maps to -1
✅ Precise bitwise transition analysis under addition of 1
✅ O(1) closed-form formula using the lowest set bit of nums[i] + 1, shifted right by one
✅ Optimal O(n) time and O(1) auxiliary space complexity
⏱️ TIMESTAMPS
00:00 Intro
01:08 Problem Understanding and Constraints
02:34 Core Observations and Mathematical Insight
03:36 Algorithmic Approach and Bit Manipulation Strategy
04:39 Line-by-Line Java Code Walkthrough
05:51 Step-by-Step Test Run and Dry Run
07:30 Time Complexity Analysis
08:13 Space Complexity Analysis
08:50 Outro and Key Takeaways
📂 Problem Folder and Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/January/21-January/3315-Construct-the-Minimum-Bitwise-Array-II
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/21-January/3315-Construct-the-Minimum-Bitwise-Array-II/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/21-January/3315-Construct-the-Minimum-Bitwise-Array-II/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/21-January/3315-Construct-the-Minimum-Bitwise-Array-II/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/21-January/3315-Construct-the-Minimum-Bitwise-Array-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, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Medium Problems
Java DSA Preparation
Bit Manipulation
Binary Invariants
Lowbit Arithmetic Tricks
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 does clearing the highest bit among the trailing 1s of nums[i] minimize the value of ans[i]?
1️⃣ Higher bit positions correspond to larger powers of 2, so subtracting them reduces the number the most
2️⃣ Clearing lower bits creates negative numbers
3️⃣ Higher bits are always 0 in prime numbers
4️⃣ It prevents integer overflow in 32-bit registers
#LeetCode3315 #LeetCode #ConstructTheMinimumBitwiseArrayII #Java #JavaDSA #BitManipulation #Array #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description