[Java] O(n) Look at the last block of ones
Intuition\nWe have prime numbers only. They all are odd except 2. For 2 we always return -1. For all the others answer exists.\nWhen we add 1 to the number what
# Intuition\nWe have prime numbers only. They all are odd except 2. For 2 we always return -1. For all the others answer exists.\nWhen we add 1 to the number what happens bitwise?\nThe last block of ones shifts by 1 position to the left.\nWe know that each number is odd - the last block always starts at the last position in bit representation. If we shift the last block by 1 to the right - after addition we\'re going to have bitwise OR equal to target and the minimal number achieving that.\n\n# Approach\nTraverse the array. For each value traverse the bit representation right to left, when we see 0 - flip the previous 1. Last value in representation is always 1, except number 2. Handle it separately.\n\n# Complexity\n- Time complexity:\n$$O(32 * n)$$\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n```java []\nclass Solution {\n    public int[] minBitwiseArray(List<Integer> nums) {\n        int[] res = new int[nums.size()];\n        for (int i = 0; i < nums.size(); i++) {\n            int x = nums.get(i);\n            if (x == 2) {\n                res[i] = -1;\n                continue;\n            }\n            for (int j = 0; j < 32; j++) {\n                if (((x >> j) & 1) == 0) {\n                    res[i] = x ^ (1 << (j - 1));\n                    break;\n                }\n            }\n        }\n        return res;\n    }\n}\n```
['Bit Manipulation', 'Java']