3314. Construct the Minimum Bitwise Array I LeetCode Solution
In this guide, you will get 3314. Construct the Minimum Bitwise Array I LeetCode Solution with the best time and space complexity. The solution to Construct the Minimum Bitwise Array I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Construct the Minimum Bitwise Array I
You are given an array nums consisting of n prime integers.
You need to construct an array ans of length n, such that, for each index i, the bitwise OR of ans[i] and ans[i] + 1 is equal to nums[i], i.e. ans[i] OR (ans[i] + 1) == nums[i].
Additionally, you must minimize each value of ans[i] in the resulting array.
If it is not possible to find such a value for ans[i] that satisfies the condition, then set ans[i] = -1.
For i = 0, as there is no value for ans[0] that satisfies ans[0] OR (ans[0] + 1) = 2, so ans[0] = -1.
For i = 1, the smallest ans[1] that satisfies ans[1] OR (ans[1] + 1) = 3 is 1, because 1 OR (1 + 1) = 3.
For i = 2, the smallest ans[2] that satisfies ans[2] OR (ans[2] + 1) = 5 is 4, because 4 OR (4 + 1) = 5.
For i = 3, the smallest ans[3] that satisfies ans[3] OR (ans[3] + 1) = 7 is 3, because 3 OR (3 + 1) = 7.
For i = 0, the smallest ans[0] that satisfies ans[0] OR (ans[0] + 1) = 11 is 9, because 9 OR (9 + 1) = 11.
For i = 1, the smallest ans[1] that satisfies ans[1] OR (ans[1] + 1) = 13 is 12, because 12 OR (12 + 1) = 13.
For i = 2, the smallest ans[2] that satisfies ans[2] OR (ans[2] + 1) = 31 is 15, because 15 OR (15 + 1) = 31.
Constraints:
1 <= nums.length <= 100
2 <= nums[i] <= 1000
nums[i] is a prime number.
Complexity Analysis
Time Complexity: O(\Sigma \log\texttt{nums[i]}) \approx O(n)
Space Complexity: O(n)
3314. Construct the Minimum Bitwise Array I LeetCode Solution in C++
class Solution {
public:
vector<int> minBitwiseArray(vector<int>& nums) {
vector<int> ans;
for (const int num : nums)
ans.push_back(num == 2 ? -1 : num - getLeadingOneOfLastGroupOfOnes(num));
return ans;
}
private:
// Returns the leading one of the last group of 1s in the binary
// representation of num. For example, if num = 0b10111, the leading one of
// the last group of 1s is 0b100.
int getLeadingOneOfLastGroupOfOnes(int num) {
int leadingOne = 1;
while ((num & leadingOne) > 0)
leadingOne <<= 1;
return leadingOne >> 1;
}
}; /* code provided by PROGIEZ */
3314. Construct the Minimum Bitwise Array I LeetCode Solution in Java
class Solution {
public int[] minBitwiseArray(List<Integer> nums) {
int[] ans = new int[nums.size()];
for (int i = 0; i < nums.size(); ++i)
ans[i] = nums.get(i) == 2 ? -1 : nums.get(i) - getLeadingOneOfLastGroupOfOnes(nums.get(i));
return ans;
}
// Returns the leading one of the last group of 1s in the binary
// representation of num. For example, if num = 0b10111, the leading one of
// the last group of 1s is 0b100.
private int getLeadingOneOfLastGroupOfOnes(int num) {
int leadingOne = 1;
while ((num & leadingOne) > 0)
leadingOne <<= 1;
return leadingOne >> 1;
}
} // code provided by PROGIEZ
3314. Construct the Minimum Bitwise Array I LeetCode Solution in Python
class Solution:
def minBitwiseArray(self, nums: list[int]) -> list[int]:
return [-1 if num == 2 else num - self._getLeadingOneOfLastGroupOfOnes(num)
for num in nums]
def _getLeadingOneOfLastGroupOfOnes(self, num: int) -> int:
"""
Returns the leading one of the last group of 1s in the binary
representation of num. For example, if num = 0b10111, the leading one of
the last group of 1s is 0b100.
"""
leadingOne = 1
while (num & leadingOne) > 0:
leadingOne <<= 1
return leadingOne >> 1 # code by PROGIEZ
