Count All Positive Integers Having N digits and the absolute difference between any two adjacent digits is K.

Recursive Approach

The solution to finding the count of Positive Integers having N digits and absolute difference K between any two adjacent digits is based on recursion, we will start iterating over [1,9] digits, and for each digit, count the number of N digits numbers having an absolute difference between adjacent digits is K. There will be two cases

Steps of Algorithm

1.  If adding K to one’s digit of the number does not exceed 9, then we will recursively call our function by decreasing N and by making number = (number*10 + number%10+ K). 
2. The other case will be, if (number%10-K>=0), then we will recursively call our function by decreasing N, and making number = (number*10 + number%10-K).
3. We also need to handle when K = 0. 
4. If K = 0, then adding or subtracting K does not make any difference, so we will call our recursive function only once in this case. 
5. Finally, we get the count of positive integers having N digits and the absolute difference between any adjacent digits of a number is K. 

Implementation in C++

// c++ Solution to find positive integers having N digits 
// and absolute difference between any two adjacent digits is K 
#include<bits/stdc++.h>
using namespace std;
void recursive_func(int n, int number,int &countNumber, int k){
    // if number is formed
    if(n==0){
        cout << number << endl;
        countNumber++;
        return;
    }
    
    // if adding K to one's digits of number is less than 10
    if((number%10 + k) <= 9){
        recursive_func(n-1, number*10 + number%10+k, countNumber, k);
    }
    
    // if K = 0, then we will call function only once,
    if(k){
        // if subtracting k from one's digit of number is positive
        if((number%10-k)>=0){
            recursive_func(n-1, number*10 + number%10- k, countNumber, k);
        }
    }
    return;
}
int main(){
    int n = 4, k = 2;
    int countNumber = 0;
    // making possible number starting from digit 1.
    
    for(int i=1;i<=9;i++){
        recursive_func(n-1, i, countNumber, k);
    }
    cout << countNumber << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Output: 

45

Complexity Analysis

Time Complexity: O(2^N)

Explanation: For every digit of the number, we have two choices either we take previousDigit+k or previousDigit-k.

Space Complexity: O(1)

Explanation: No extra Space is required. 

Frequently asked questions

Q1. Why are prime numbers? 

Ans: According to the definition of the prime number, a prime number should exactly have 2 factors, i.e., 1 and number itself. Ex: 2,3,5,7 and so on. 

Q2. How many distinct numbers are possible of length N, if the formed number should be a binary, decimal, and hexadecimal number?

Ans: The total number of distinct digits of length N = (digits allowed)^N. 

In the case of binary, digits allowed = 2, so total distinct numbers = 2 ^ N. 

In the case of decimal, digits allowed = 10, so total distinct numbers = 10^N. 

In the case of hexadecimal, digits allowed = 16, so total distinct number = 16^N. 

Q3. How many subsets are possible of an array of length N?  

Ans: There are 2^N possible subsets of an array of length N. 

Key takeaways

In this article, we discussed the problem of finding the count of all positive integers having N digits, and the absolute difference between two adjacent digits is K. We hope you understand the problem and solution properly. Now you can do more similar questions. 

If you are a beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free! 

Check out this problem - Two Sum Problem

Thank you for reading. 

Until then, Keep Learning and Keep Coding.