Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
Problems based upon bitwise operations are very commonly asked in programming interviews so it becomes increasingly necessary to practice array problems which include various techniques and algorithms.
So why to wait. Let’s jump to the problem statement.
Problem Statement
We have an integer N. Our task is to count the number of N-digit values such that the bitwise AND of adjacent digits equals 0.
Example
Input
N=2
Output
41
Explanation
There are 41 two-digit numbers where bitwise AND results in 0.
All the two-digit numbers will lie in the range [10,99] both inclusive and for each of them, check if the AND of the adjacent digits is equal to 0.
Like, say for 10, there are 2 digits, 1 and 0; if we do 1&0, this returns 0, so 10 is a valid number.
For a number, say 25, the digits are 2 and 5. If you perform AND of 2 and 5 -
010
AND 101
——————————————
000
So, 25 is also a valid number.
There are 41 different two-digit numbers whose bitwise AND is 0.
Brute Force Approach
The most obvious approach is that we iterate over all the N-digit numbers, and then for each number, we calculate the bitwise AND of all of their adjacent digits. Then we only count those numbers whose bitwise AND of all the adjacent digits turns out to be 0.
Algorithm
Initialize N and a function “count” that calculates the 2-digit numbers whose bitwise AND of adjacent digits equals 0.
Get the lowest N digit number, ”L” by calculating the pow(10, N-1).
Get the highest N digit number, “R” by calculating the pow(10, N) - 1.
Iterate from L to R and for each number, check if bitwise AND of adjacent digits results in zero or not.
If, bitwise AND is 1, increment the ans to 1.
Finally, return the answer.
Dry Run
First initialize N = 2 and initialize a function “count” that calculates the 2 digit numbers whose bitwise AND of adjacent digits equals 0.
Here, N is not equal to 1.
Therefore, L is set to ‘pow(10, N-1)’ which is ‘pow(10, 1)’. Here, L=10.
R is set to ‘pow(10, N) - 1’ which is ‘pow(10, 2) - 1’. Here, R=99.
Initialize ‘ans’ to 0. We need to calculate all the 2 digit numbers with bitwise AND of adjacent digits equal to 0 such that the numbers lie between 10 and 99 (both inclusive).
Iterate over all the numbers from L to R and convert each number to a string ‘s’. With the help of another loop check the bitwise AND of adjacent digits.
If the bitwise AND of any two numbers is not 0, the ‘flag’ is set to false and the loop is broken. Some of the numbers where bitwise AND of adjacent digits is not 0 are:
N
First digit of N
(in binary)
Second digit of N (in binary)
Bitwise AND
11
001
001
001
23
010
011
010
53
101
011
001
89
1000
1001
1000
If the flag is still true, increment the ‘ans’ to 1. Some of the numbers where bitwise AND of adjacent digits is 0.
N
First digit of N
(in binary)
Second digit of N (in binary)
Bitwise AND
10
001
000
000
12
001
010
000
25
010
101
000
48
0100
1000
0000
5. Finally, the result we will get after all the iterations is 41 which are the different two-digit numbers whose bitwise AND is 0.
Code in C++
#include<bits/stdc++.h>
using namespace std;
int count(int N){
// Base case
if(N==1){
return 10;
}
// Lowest N-digit number
int l = pow(10, N - 1);
// Highest N-digit number
int r = pow(10, N) - 1;
// Stores the count
int ans = 0;
// Iterate over all N-digit numbers
for(int i = l; i <= r; i++){
string s = to_string(i);
// Iterate over all digits
bool flag=true;
int digit;
/*
Loop to check if the bitwise AND
of adjacent digits is 0 or not
*/
for(int j=1;j<N;j++){
digit=(s[j-1]-'0') & (s[j]-'0');
if(digit){
flag=false;
break;
}
}
// If flag is still true, increment ans.
if(flag){
ans++;
}
}
return ans;
}
int main(){
int N = 2;
// Call the function and print the result
cout<<count(N);
return 0;
}
You can also try this code with Online C++ Compiler
For a given value of N, there are total 10N N-digit numbers (as for each of the N positions of an N-digit number you have 10 choices i.e., 0 to 9 so the total count of N-digit numbers becomes 10 x 10 x …..10 N times which is 10N ), and for each number, we have a for loop of length N that checks the bitwise AND of all of its adjacent digits.
Space Complexity = O(1)
Because we have only a few variables that take a constant space of O(1).
Recursion Approach
If we look at the above solution carefully, we can observe that we can also proceed in the reverse order. Thus, we can create valid N-digit numbers rather than checking the number for validity. We can achieve this using recursion.
Algorithm
Define a recursive function, such as count(currentPos, prev, N) where “currentPos” ranges from 1 to N and denotes the position within the number. “prev” stores the previous digit in the number. The function returns the total count of (N+1-currentPos) digit valid numbers when we consider “prev” as the previous digit
If the currentPos equals ‘N + 1’, return 1. This is because a legitimate N-digit number has been produced as we have reached the N+1th position after forming the N-digit number.
If currentPos=1, which means we are at the first position of a number. Any number can’t start with 0. So, for the first position i.e., currentPos=1 there are 9 choices of digits from 1 to 9. But if N = 1 i.e., we are looking for a 1 digit number, then 0 is a valid number so 0 can be present at the first position.
Otherwise, for any value of currentPos, traverse through all the numbers currDigit from 0 to 9, check if the condition (currDigit & prev) == 0) holds true or not, and accordingly place satisfying currDigit values in the current position.
Recursively call the count function for index (currentPos + 1) after making a valid placement of digits.
Dry Run
First, we need to call the count function with currentPos=1, prev=0 and n=2.
Since currentPos is 1, we enter the if condition and loop runs from i=1 to i=9.
We call the count function recursively with currentPos=2 and ‘i’ as the new prev value.
Function “count(2, 1, 2)” results in currentPos being 2 and prev being 1. Loop from 0 to 9 times when entering the second condition.
Verify that each digit's bitwise AND with preceding is 0. Any digit that has its first (least significant) bit set to 1 will not satisfy the criterion since 1 in binary is 001 and 0 in binary is 000.
Therefore, it will only count the even digits (0, 2, 4, 6, 8). Recursively call the count method, passing in the digit as the new prev and currentPos + 1.
currentPos is now 2, and prev is 2 for count(2, 2, 2). Only the digits with their second bit set to 0 will satisfy the criteria because 2 in binary is 010. So, the numbers 0, 1, 4, 5, 8, and 9 will be added together.
Recursively call the count method, passing in the digit as the new prev and currentPos + 1. Include the outcome in the ‘val’ variable.
Because of this, val += count(3, 0, 2) + count(3, 1, 2) + count(3, 4, 2) + count(3, 5, 2) + count(3, 8, 2) + count(3, 9, 2).
4. Repeat steps 3-4 for all remaining digits in the loop from step 2.
5. Finally, val = 41, which is the total number of two-digit numbers whose bitwise AND is 0.
Code in C++
#include<bits/stdc++.h>
using namespace std;
int count(int currentPos, int prev, int n){
/*
If currentPos= n + 1, a valid
n-digit number has been formed
*/
if (currentPos == n + 1){
return 1;
}
/*
If current position is 1,
then any digit from [1-9] can be placed.
If n = 1, 0 can be also placed.
*/
int val=0;
if (currentPos == 1){
for (int i = (n == 1 ? 0 : 1); i <= 9; ++i) {
val += count(currentPos + 1, i, n);
}
}
/*
For remaining positions,
any digit from [0-9] can be placed
after checking the conditions.
*/
else{
for (int i = 0; i <= 9; ++i){
// Check for bitwise AND
if ((i & prev) == 0){
val += count(currentPos + 1, i, n);
}
}
}
// Return answer
return val;
}
int main(){
int N = 2;
// Call the function and print the result
cout << count(1, 0, N) << endl;
}
You can also try this code with Online C++ Compiler
Since we generate a total of 10N numbers and use recursion, we call 10N recursion stacks to generate all numbers. So it is the time complexity of O(10N).
Space Complexity = O(10N)
Since we generate a total of 10N numbers and use recursion, we call 10N recursion stacks to generate all numbers. So it is stack space of O(10N).
If we look at the above solution carefully, we can observe repeated subproblems. We had to keep in mind that whenever we encounter repeated subproblems in recursion, we can further optimize the solution through dynamic optimization.
Algorithm
Define a recursive function, such as count(currentPos, prev, N) where currentPos ranges from 1 to N and denotes the position within the number. “prev” stores the previous digit in the number. The function returns the total count of (N+1-currentPos) digit valid numbers when we consider “prev” as the previous digit.
If the currentPos equals N + 1, return 1 because this means we have reached the (N+1)th position after forming the N-digit number.
If state dp[currentPos][prev] is already computed then return this state dp[currentPos][prev].
If currentPos=1, which means we are at the first position of a number. Any number can’t start with 0. So, for the first position i.e., currentPos=1 there are 9 choices of digits from 1 to 9. But if N = 1 i.e., we are looking for a 1 digit number, then 0 is a valid number so 0 can be present at the first position.
Otherwise, for any value of currentPos, cycle through all the numbers i from 0 to 9, check if the condition (i & prev) == 0) holds true or not, and accordingly place satisfying i values in the current position.
Recursively call the count function for index (currentPos + 1) after making a valid placement of digits and store the result in dp[currentPos][prev].
Dry Run
With n = 2, the function countValidNDigitNumbers() is called, requiring us to count the number of valid 2-digit numbers.
Using the memset() function, the function sets the dp array's value to -1 in the dp[][] array.
The count() function is then called with the arguments currentPos= 1, prev = 0, and n = 2.
The first thing that is to check in the count() function is whether or not the currentPos is equal to n + 1. Since currentPos equals 1 and n equals 2, currentPos cannot be equal to n + 1, and the function remains in place.
The value of dp[currentPos][prev] is then checked to see if it has previously been calculated. The function continues to calculate the value because it hasn't been calculated yet (because it was initialized to -1 in the main() method).
The function enters the first if condition, which sets the initial value of i to 1, because currentPos is equal to 1.
The count() function is called recursively for each iteration with the arguments currentPos + 1, i, and n in the for-loop, which has a range of 1 to 9 (inclusive). The count() function's output value is added to val.
For i = 1, i = 2, i = 3,..., and i = 9, recursively calling the count() function takes place. The count() function is called with the arguments currentPos = 2, prev = 1, and n = 2 for i = 1.
The count() function is used with the parameters currentPos = 2, prev = 2, and n = 2 with the value of i = 2.
The count() function is called with the arguments currentPos = 2, prev = 0, and n = 2 for i = 3.
The count() function is called with the arguments currentPos = 2, prev = 0, and n = 2 for i = 4. And so on...
The count() function then returns the value of ‘val’. The number of 2-digit numbers is 41, which is the value of val.
Code in C++
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAX_DIGITS = 10000;
const int NUM_DIGITS = 10;
// dp array to store intermediate results
int dp[MAX_DIGITS][NUM_DIGITS];
// Function to count the number of n-digit numbers
int count(int currentPos, int prev, int n){
/*
If digit = n + 1, a valid
n-digit number has been formed
*/
if (currentPos == n + 1){
return 1;
}
int& val = dp[currentPos][prev];
if (val != -1){
return val;
}
val = 0;
/*
If current position is 1,
then any digit from [1-9] can be placed.
If n = 1, 0 can also be placed.
*/
if (currentPos == 1){
int start = (n == 1) ? 0 : 1;
for (int i = start; i <= 9; ++i) {
val += count(currentPos + 1, i, n);
}
}
/*
For remaining positions,
any digit from [0-9] can be placed
after checking the conditions.
*/
else{
for (int i = 0; i <= 9; ++i) {
// Check for bitwise AND
if ((i & prev) == 0) {
val += count(currentPos + 1, i, n);
}
}
}
// Return answer
return val;
}
/*
Function to count the number of n-digit numbers
using dynamic programming
*/
int countValidNDigitNumbers(int n){
// Initialize dp array with -1
memset(dp, -1, sizeof dp);
/*
Call count function to count
the number of n-digit numbers
*/
return count(1, 0, n);
}
// Driver code
int main(){
int n = 2;
// Call the function and print the result
cout<<countValidNDigitNumbers(n)<<endl;
return 0;
}
You can also try this code with Online C++ Compiler
Since we are only generating numbers to fill in the dynamic array, so for each value of “digit” and “prev”, we have a number that can be a maximum of O(N x 10 ).
Space Complexity = O(N × 10)
Since we only need a dp array of size (N x 10).
Frequently Asked Questions
What is dynamic programming?
It is a method of solving complex problems by breaking them down into smaller, simpler subproblems and solving each subproblem only once.
What is memoization?
Memoization is a method of storing the outcomes of computationally expensive function calls and retrieving the cached results when the function is called again with the same inputs.
What is a bitwise AND operator?
The bitwise AND operator is represented by the symbol ‘&’. It gives 1 when both the bits are 1 and 0 otherwise.
What is a bitwise OR operator?
The bitwise OR operator is represented by the symbol ‘|’. It gives 1 when one of the bits is 1 and 0 otherwise.
What is the bitwise XOR operator?
The bitwise XOR operator is represented by the symbol ‘^’. It gives 1 when corresponding bits in the operand are different and 0 otherwise.
Conclusion
In this blog, we discuss the problem of counting N-digit numbers whose bitwise AND of adjacent digits equals 0. We have implemented the problem in C++ programming language.
For more dynamic programming articles, you can refer following links: