Bit manipulation || beats 100% || very easy, simple analysis || c++
IntuitionOur intution is based on observing a pattern.
If the number is even then no solution is possible. We can prove this by contradiction, suppose we get a
![image.png](https://assets.leetcode.com/users/images/7effbc23-c386-41e0-b591-7780d728e61b_1742066966.7074153.png)

# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Our intution is based on observing a pattern.
If the number is even then no solution is possible. We can prove this by contradiction, suppose we get a no (say k) such that k | k+1 = v, where v belongs to nums and is even. Two cases are possible:
1. If the lsb of k is 0 then lsb of k+1 should be 1 (which means if k is even then K=1 has to be odd) 
OR
2. If k is odd then k+1 should be even. 

So if we or the least significant bits of any no. (here k) with its next higher integer then the lsb will always be 1 (0 | 1 : in first case, 1 | 0 in the second case). Any even no will never have it's lsb==1. So for even v no such k exists.

If the no. is odd then one soltuion always exists that is equal to no. - 1 as if we substract 1 from an odd no. then we get the lsb toggled while keeping the rest of the bits same. But there can be one more solution. For eg. take 11, 10 | 11 will give u 11 but so will 9 | 10. If we expand 11 in binary we get 1011. 9 in binary is 1001 which is formed by unsetting the rightmost bit after first unset bit.
Similarly for 101**01**11 the answer would be 101**00**11. This is because 111 of 1010**111** can be written as => **011 + 1**.  011 belongs to 1010**011** and adding a 1 to this no would give us 1010100 and or of these two nos will give the result 1010111.

# Approach
<!-- Describe your approach to solving the problem. -->
We will traverse in the array nums and first check the parity of the number. If the number is even then push back in the answer array -1. if the no is odd then we need to find the ith bit at which the we get the first 0. It means that from the i-1 th bit to the lsb we have all ones in the binary representation of the number. To toggle the i-1 th bit we can xor the original number with a number that has only the i -1 th bit set. 
  **1010111 ^ 0000100  =  1010011**
0000100 is number that is power of two. Any number which has one bit set is a power of two. So we can right shift 1 by i-1 no. of places to get this number and xor it with the original integer. 


# Complexity
- Time complexity:  O(n*log(k)) where k = no of bits in every integer
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(n)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    vector<int> minBitwiseArray(vector<int>& nums) {
        vector<int> ans;
        for(int num: nums){
            // if even no such no. exists, so -1
            if(! (num & 1) )  ans.push_back(-1);
            // if no. is odd
            else{
                int i=0;        // i carries the bit index. Initially 0.
                int n = num;       // n is a copy if num.
                while(n){
                    // while u are getting a 1 at lsb, keep looping
                   if(n & 1)    {
                    i++;        // increment i
                    n = n>>1;   // left shift to get the next bit as lsb
                   }
                   else{
                    // i bits were one, so we need to toggle the i th bit for which we need 1 only at the i th bit, this can be done by right sift operator
                   int  p= 1<< (i-1); // cout<<p<<" "<<i<<" "<< n<<endl;
                  // xor the value to get the no.   
                    n = num^p; 
                    // we have found the result so break. n contains the result
                    break;
                   } 
                }
                
                if(n!=0)    ans.push_back(n);
                // if n==0 => n is 2^k -1 type of a no. If the loop broke because n==0 then else part in the
                // while loop would not have been calculated. A no. for which all the bits are ones (2^k -1)
                // the optimal soln is the number formed by taking all the bits except msb that can be done by 
                // dividing the original no. by 2 (it's equivalent is left shift the no. by 1)
                else    ans.push_back(num>>1);
            }
        }
        return ans;
    }
};
```
['C++']