Count of N-digit Numbers whose bitwise AND Of Adjacent Digits Equals 0

Rhythm Jain
Last Updated: May 13, 2022

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.

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:

Assume we have the following input -

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] 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 :

2→ 010
5→ 101

        010

AND    101
__________
        000

So, 25 is also a valid number.

 

But 887 is not valid because:

8 AND 8 is: 1000 AND 1000 = 1000 which is not zero. 

8 AND 7 is: 1000 AND 0111 =  0000 which is zero. 

Since the AND of all adjacent digits is not zero, so 887 is not valid.

Approach 1: Brute Force

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:

  • Get the lowest N digit number,” L”. 
  • Get the highest N digit number, “R”.
  • Iterate from L to R and for each number check if bitwise AND of adjacent digits results in zero or not.

Code

#include<bits/stdc++.h>
using namespace std;


int count(int N)
{
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;
        for(int j=1;j<N;j++){
            digit=(s[j-1]-'0') & (s[j]-'0');
            if(digit){
                flag=false;
                break;
            }
        }
        if(flag) ans++;
}
return ans;
}


int main()
{
int N = 2;

cout<<count(N);
return 0;
}


Output

41

Complexity Analysis

Time Complexity: O(N × 10N)

For a given value of N, there are total 10N-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 10x10x…..10 N times which is 10), 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).

Approach 2: Recursion

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 because a legitimate N-digit number has been produced because this means 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 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 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 digit.

Code

#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;
	cout << count(1, 0, N) << endl;
}


Output

41

Complexity Analysis

Time 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 the time complexity of O(10N)

Space Complexity: O(10N

Since we generate a total of 10N numbers and use recursion, we call 10recursion stacks to generate all numbers. So it is stack space of O(10N)

Approach 3: Dynamic Programming

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.


We can further implement memoization for the above solution using a 2D dp array (since we only have two states that vary in a recursive function, digit and prev).

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 a legitimate N-digit number has been produced because this means we have reached the N+1th 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 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 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 digit and store the result in dp[currentPos][prev].

Code

#include<bits/stdc++.h>
using namespace std;

int dp[10000][10];

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 be also placed.
	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 dp[currentPos][prev]=val;
}

// Driver code
int main()
{
    memset(dp, -1, sizeof dp);
	int N = 2;
	cout << count(1, 0, N) << endl;
}


Output

41

Complexity Analysis

Time Complexity: O(N × 10)

Because 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) 

Because we only need a dp array of size (N X 10).

Frequently Asked Questions

  1. How to convert the recursive solution to a dynamic approach-based solution?
    In the recursive solution, if we can observe repeated states, that solution can be further optimized by applying memoization. The memoization-based solution can be converted to a dynamic programming approach. 
    For more insights about memoization and dynamic programming, you can visit here.
     
  2. What do you mean by Dynamic Programming?
    Dynamic Programming or DP is a specialized algorithm paradigm in computer science. This technique solves an optimization problem by breaking it down into simpler subproblems. We do so by keeping in mind that the optimal solution to the overall problem depends on optimal subproblem solutions.

Key Takeaways

Bitwise operations are straightforward. They are often favored over traditional arithmetic operations since they are faster and utilize less memory.

Dynamic Programming always reduces enormous time complexities and provides us with the most efficient solution. But note that dynamic programming can only be applied when we observe repeated sub-problems.

You can study more about Dynamic Programming by visiting ‘Dynamic Programming and Algorithms.’

If you wish to practice questions based on Dynamic Programming, you can visit Top Dynamic Programming Questions.

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think