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*2N).
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 2n-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;
}

You can also try this code with Online C++ Compiler
Run Code
Output
The total number of subsequences with odd Bitwise AND value is 7

You can also try this code with Online C++ Compiler
Run Code
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: [-231,231-1], whereas the 32-bit unsigned integer could have integer values in the range [0,232-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!