Construct Minimum Bitwise Array with Prime Numbers

🚀 Day 34/100 of My LeetCode Challenge – Solved "Construct the Minimum Bitwise Array I"! 🎯 Today’s problem presented an elegant bitwise puzzle that combined logical reasoning with systematic exploration. The task: Given an array of prime integers, construct another array where for each index i, the bitwise OR between ans[i] and ans[i] + 1 equals nums[i], while minimizing each ans[i]. If impossible, return -1. 🔍 Key Insight: The relationship x | (x + 1) == nums[i] has a special property: x | (x + 1) produces a binary number with consecutive ones from the least significant bit upward. For example: 1 | 2 = 3 (binary 01 | 10 = 11) 4 | 5 = 5 (binary 100 | 101 = 101) This means nums[i] must be of the form where all bits after the first zero from LSB are set to 1. ⚡ My Approach: I implemented a straightforward yet efficient solution: Iterate through each prime in the input array. For each, test all possible x from 1 to nums[i]-1. Check if x | (x + 1) equals the target. Track and return the smallest valid x (or -1 if none exists). ✅ Result: Runtime: 3 ms (faster than 57.02% of submissions) Memory: 46.79 MB (better than 49.12%) All 658 test cases passed! 💡 Takeaway: Sometimes the most direct approach—brute force within reasonable bounds—is both clean and effective, especially when constraints are small (nums[i] ≤ 1000). Understanding bitwise properties helps verify correctness and could inspire optimizations for larger scales. This daily practice continues to sharpen my problem-solving skills, reinforcing that even "simple" problems can teach valuable lessons about constraints, efficiency, and mathematical insight. #LeetCode #100DaysOfCode #BitwiseOperations #Algorithm #Java #CodingChallenge #ProblemSolving #TechJourney #SoftwareEngineering #LearnInPublic #CodingLife

  • graphical user interface

To view or add a comment, sign in

Explore content categories