Rust/Python. Real linear solution with full explanation
Intuition\n\nFirst we need to understand that the question asks to solve equation:\n\nx OR (x + 1) = y\n\nfor x. Here they have a strange requirement of y being
# Intuition\n\nFirst we need to understand that the question asks to solve equation:\n\n`x OR (x + 1) = y`\n\nfor `x`. Here they have a strange requirement of `y` being prime, but we later we will see that it is irrelevant. On top of this the `x` should be as small as possible.\n\n\nLets look at some number `10111001111` and after trying multiple numbers you can see that all you need is to find how many consequitive ones from the right do you have (in our case it is 4: `1111`) and remove the top one -> `0111`. So your number will be:\n\n```\n10111001111\n= \n10111000111 \nOR\n10111001000\n```\nIt is easily to see that this will work (when you have some ones at the end) as `1...1` or `1..1 + 1` will give you `11...1`.\n\nAs you see here it will work for any number and for even you never can find the solution.\n\n------\nSo we have the solution. Now we can easily implement this with a loop:\n\n```\n  def find_x(self, y):\n    if y % 2 == 0:\n      return -1\n\n    count, temp = 0, y\n    while temp & 1:\n      count += 1\n      temp >>= 1\n\n    mask = 1 << (count - 1)\n    return y & ~mask\n```\n\nBut we do not want a loop. We need efficient binary operation. And you can achieve it with `x & ((x | ~(x + 1)) >> 1)`. This will work because:\n\n - `x + 1` changes your `1..1` to `10..0`\n - `!(x + 1)` inverts bits of that value\n - `(x | !(x + 1))` all trailing ones are still ones then zero and then once again\n - prev expression >> 2 just shifts one value to the right\n - x & prev expression gets you the number you want\n \n# Complexity\n- Time complexity: $O(n)$\n- Space complexity: $O(n)$\n\n# Code\n```python []\nclass Solution:\n\n  def find_x(self, x):\n    if x % 2 == 0:\n      return -1\n    return x & ((x | ~(x+1)) >> 1)\n\n  def minBitwiseArray(self, nums: List[int]) -> List[int]:\n    return [self.find_x(v) for v in nums]    \n```\n```rust []\nimpl Solution {\n    fn find_x(x: i32) -> i32 {\n      if x % 2 == 0 {\n          return -1;\n      }\n      x & ((x | !(x + 1)) >> 1)\n    }\n\n    fn min_bitwise_array(nums: Vec<i32>) -> Vec<i32> {\n      nums.into_iter().map(|v| Self::find_x(v)).collect()\n    }\n}\n```\n\n**BTW, rust has** `trailing_ones()` function so you can just do:\n\n`x & !(1 << (x.trailing_ones() - 1))`. But I am not sure what ASM code will it generate. So if Rust experts are here, can you tell if it gives an efficient implementation.
['Python3', 'Rust']