Find the total number of subsequences having odd Bitwise OR values in the array

Approach

The naive approach is to find all the subsequences and calculate the bitwise OR 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 when either bit is set, i.e., 1|0 = 1 and 1|1 = 1. Therefore, the bitwise | (OR) operator, when applied between 2 integers, will always be odd only if either of the integers is odd. Hence, for a subsequence to have an odd Bitwise OR value, subsequence should have at least an odd integer. 

Since we know the total number of non-empty subsequences for an array of size n is 2ⁿ-1. 

Therefore: the total number of subsequences with odd Bitwise OR value 
= Total number of non-empty subsequences containing only odd integers * Total number of subsequences containing only even integers
= (2^odd_no-1)*2^even_no, where odd_no = total number of odd integers in the array and even_no = total number of even integers in the array. 

Code in C++

#include<iostream>
#include<vector>
using namespace std;

int countSubsequences(vector<int>& arr){
	int odd_no = 0;
	int even_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++;
		}else{
			even_no++;
		}
	}
	
	int total_count = ((1<<odd_no)-1)*(1<<even_no);
	return total_count;
}

int main(){
	vector<int> arr{3,5,6};
	cout<<"The total number of subsequences with odd Bitwise OR 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 OR value is 6

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 OR operation between 2 numbers?

The time complexity of an OR 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³¹,2³¹-1], whereas the 32-bit unsigned integer could have integer values in the range [0,2³²-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 OR 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 - Search In Rotated Sorted Array

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!