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 (no such value exists).
- 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

[{"language":"C++","code":"class Solution {\npublic:\n    vector<int> constructArray(vector<int>& nums) {\n        vector<int> ans;\n        for (int x : nums) {\n            int a = -1;\n            if (x == 2) a = -1;\n            else if ((x - 1 | x) == x) a = x - 1;\n            else if ((x | (x - 1)) == x) a = x - 2;\n            ans.push_back(a);\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">    vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">> </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">constructArray</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> nums</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">        vector</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;int></span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> ans;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        for</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> (</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> x : nums) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">            int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> a </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#D73A49;--shiki-

Related Tags