Table of contents
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.
Frequently Asked Questions
6.
Key Takeaways
Last Updated: Mar 27, 2024

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

Author Gaurish Anand
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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

Problem Statement

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

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


Input: array = {4,1,2,3,5}
Output: 7
Explanation: {1}, {3}, {5}, {1,3}, {1,5}, {3,5}, {1,3,5} are the 7 subsequences in the above array whose bitwise AND value is odd 

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!

Live masterclass