1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Efficient Approach
4.
Code in C++
4.1.
Output
4.2.
Time Complexity
4.3.
Space Complexity
5.
6.
Key Takeaways
Last Updated: Mar 27, 2024

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

Gaurish Anand
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

## Introduction

Bitwise Algorithms are used to perform operations on bits. Bitwise operations are much faster and are sometimes even used to improve the efficiency of a program.

Itâ€™ll be necessary to think about data at the bit level on occasion, and we'll have to work with each data bit separately. To make our activity more manageable, we may need to use binary operators to turn on/off particular data bits. Six major binary operators that make it easy to conduct operations and change data bits are:

1. & (Bitwise AND)
2. | (Bitwise OR)
3. ^ (Bitwise XOR)
4. << (Left shift)
5. >> (Right shift)
6. ~ (Bitwise NOT)

You can go through this article to learn more about the above binary operators. In this blog, we will be discussing a problem where we will be working with | operator (Bitwise OR).

## Problem Statement

Find the total number of subsequences in an array such that the bitwise OR value of those subsequences is odd. Example :

Input: array = {4,6,3}
Output: 4
Explanation: {3}, {6,3}, {4,3} and {4,6,3} are the 4 subsequences in the above array whose bitwise OR value is odd

Input: array = {3,5,6}
Output: 6
Explanation: {3}, {5}, {3,6}, {5,6}, {3,5} and {3,5,6} are the 6 subsequences in the above array whose bitwise OR value is odd

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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*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 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 2n-1.

Thereforethe 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
= (2odd_no-1)*2even_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);
}

int main(){
vector<int> arr{3,5,6};
cout<<"The total number of subsequences with odd Bitwise OR value is "<<countSubsequences(arr)<<endl;
}

### 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).

Check out this : Longest common subsequence

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: [-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 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!

Live masterclass