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

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

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

  1. 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.
  2. Return the array ans.

Code

 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
}
 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;
    }
}
 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()
    }
}
 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
 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()
    }
}
 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.