Problem#
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
.
Examples#
Example 1#
1
2
3
4
5
6
7
8
9
10
11
|
Input: nums = [2,3,5,7]
Output: [-1,1,4,3]
Explanation:
* 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`.
|
Example 2#
1
2
3
4
5
6
7
8
9
10
|
Input: nums = [11,13,31]
Output: [9,12,15]
Explanation:
* 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.
Solution#
Method 1 – Bitwise Properties and Greedy Construction#
Intuition#
For each prime number nums[i], we want to find the smallest integer ans[i] such that ans[i] | (ans[i] + 1) == nums[i]. Since nums[i] is prime, its binary representation is a sequence of 1s followed by 0s. The minimal ans[i] is the largest even number less than nums[i] such that ans[i] | (ans[i] + 1) == nums[i].
Approach#
- For each nums[i]:
- If nums[i] == 2, ans[i] = 1 (since 1 | 2 == 3 != 2, so not possible, so ans[i] = -1).
- For odd nums[i], check if (nums[i] - 1) | nums[i] == nums[i]. If so, ans[i] = nums[i] - 1.
- For even nums[i], check if nums[i] | (nums[i] - 1) == nums[i]. If so, ans[i] = nums[i] - 2.
- If no such ans[i] exists, set ans[i] = -1.
- Return the array ans.
Code#
C++#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
vector<int> constructArray(vector<int>& nums) {
vector<int> ans;
for (int x : nums) {
int a = -1;
if (x == 2) a = -1;
else if ((x - 1 | x) == x) a = x - 1;
else if ((x | (x - 1)) == x) a = x - 2;
ans.push_back(a);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
func ConstructArray(nums []int) []int {
ans := make([]int, len(nums))
for i, x := range nums {
a := -1
if x == 2 {
a = -1
} else if (x-1)|x == x {
a = x - 1
} else if x|(x-1) == x {
a = x - 2
}
ans[i] = a
}
return ans
}
|
Java#
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public int[] constructArray(int[] nums) {
int[] ans = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
int x = nums[i], a = -1;
if (x == 2) a = -1;
else if ((x - 1 | x) == x) a = x - 1;
else if ((x | (x - 1)) == x) a = x - 2;
ans[i] = a;
}
return ans;
}
}
|
Kotlin#
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
fun constructArray(nums: IntArray): IntArray {
return nums.map { x ->
when {
x == 2 -> -1
(x - 1 or x) == x -> x - 1
(x or (x - 1)) == x -> x - 2
else -> -1
}
}.toIntArray()
}
}
|
Python#
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def constructArray(self, nums: list[int]) -> list[int]:
ans = []
for x in nums:
a = -1
if x == 2:
a = -1
elif (x - 1 | x) == x:
a = x - 1
elif (x | (x - 1)) == x:
a = x - 2
ans.append(a)
return ans
|
Rust#
1
2
3
4
5
6
7
8
9
10
|
impl Solution {
pub fn construct_array(nums: Vec<i32>) -> Vec<i32> {
nums.into_iter().map(|x| {
if x == 2 { -1 }
else if (x - 1 | x) == x { x - 1 }
else if (x | (x - 1)) == x { x - 2 }
else { -1 }
}).collect()
}
}
|
TypeScript#
1
2
3
4
5
6
7
8
9
10
|
class Solution {
constructArray(nums: number[]): number[] {
return nums.map(x => {
if (x === 2) return -1;
if ((x - 1 | x) === x) return x - 1;
if ((x | (x - 1)) === x) return x - 2;
return -1;
});
}
}
|
Complexity#
- ⏰ Time complexity:
O(n)
, where n is the length of nums. Each element is processed once.
- 🧺 Space complexity:
O(n)
, for the output array.