**Approach**

The naive approach is to find all the subsequences and calculate the bitwise AND of all the subsequences to count the required answer. The time complexity of this approach will be O(N*2^{N}).

**Efficient Approach**

Since we know, if an integer value is odd, the least significant bit of that integer will be a set bit. We also know & operator returns true only if both the bits are set, i.e., 1&1 = 1.

Bitwise & operator applied between an even integer and an odd integer will always give us an even integer. The least significant bit of an even integer is 0, whereas the least significant bit of an odd integer is 1. Since 0&1 = 0, the resultant integer will be an even integer as its least significant bit will be 0.

Therefore bitwise & operator applied between 2 integers will always be odd only if both the integers are odd. Hence, for a subsequence to have an odd Bitwise AND value, all the subsequence elements must be odd.

Since we know the total number of non-empty subsequences for an array of size n is 2^{n}-1. Therefore** the total number of subsequences with odd Bitwise AND value will be 2**^{(odd_no)}-1 **where odd_no = total number of odd integers in the array. **

Also see, __Euclid GCD Algorithm__

**Code in C++**

```
#include<iostream>
#include<vector>
using namespace std;
int countSubsequences(vector<int>& arr){
int odd_no = 0;
for(int i=0;i<arr.size();i++){
// to check if a number is odd, just check if the least significant bit is 1.
if((arr[i]&1)==1){
odd_no++;
}
}
//
int total_count = (1<<odd_no)-1;
return total_count;
}
int main(){
vector<int> arr{4,1,2,3,5};
cout<<"The total number of subsequences with odd Bitwise AND value is "<<countSubsequences(arr)<<endl;
}
```

**Output**

`The total number of subsequences with odd Bitwise AND value is 7`

**Time Complexity **

Since we are traversing the array just once, the time complexity is O(N), where N = size of the array.

**Space Complexity **

Since we are not using any extra auxiliary space, space complexity is O(1).

Read about __Bitwise Operators in C__ here.

Check out this :** **__Longest common subsequence__

**Frequently Asked Questions**

**What is the difference between bitwise AND operation and bitwise OR operation?**

When both operands are true, the AND (&) operator returns true; otherwise, it returns false. The OR (|) operator returns true when either operand is true.

**What is the C++ time complexity of an AND operation between 2 numbers?**

The time complexity of an AND operation between 2 numbers is O(1).

**What is the difference between signed int and an unsigned int?**

The 32-bit signed integer data type could hold integer values in the range: [-2^{31},2^{31}-1], whereas the 32-bit unsigned integer could have integer values in the range [0,2^{32}-1]. Since an unsigned integer canâ€™t hold negative values, it doesnâ€™t have the rightmost bit as a signed bit.

**Is there anything more in Coding Ninjas Studio that deals with Data Structures and Algorithms?**

Yes, __Coding Ninjas Studio__ offers both coding practice and frequently asked interview questions. The more we practice, the greater our chances of landing a job at our ideal organization.

**Key Takeaways**

This article taught us how to determine the total number of subsequences having odd bitwise AND values in an array.

Since questions based on Bit manipulation are frequently asked in coding rounds for various companies, we recommend you practice more problems based on __Bit manipulation__ on Coding Ninjas Studio.

Check out this problem - __XOR Queries On Tree__

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our __Online Mock Test Series__ on __Coding Ninjas Studio__** **now!