Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Recursive Approach
3.1.
Steps of Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently asked questions
5.
Key takeaways
Last Updated: Mar 27, 2024
Hard

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

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

Problem Statement

The problem states we have to find the count of positive integers having N digits and the absolute difference between any two adjacent digits is K. 

Adjacent digits are digits when the absolute difference between the position of any two digits is equal to 1.

Sample Examples

Example 1:

Input : N = 4, K = 8 
Output: 3 

Explanation: The numbers Having 4 digits and the absolute difference of 8 between adjacent digits are 8080, 9191, 1919. 

 

Example 2:

Input : N = 4, K = 2
Output: 45

Brute Force Approach

In the naive approach, we will generate all the N digit numbers and check for each generated digit, whether the absolute difference between each digit is k or not. 

Steps of Algorithm

  1. Generate all possible N digits numbers using recursion 
  2. Check for each N digit number formed if the absolute difference between adjacent digits is equal to k. 
  3. If The number satisfies the condition, increase the count. 
  4.  Print the final Count. 

Implementation in C++

#include<bits/stdc++.h>
using namespace std;
// function to check if the absolute difference
// between adjacent digits is equal to k or not
int check(int n, int k){
    while(n>9){
        int a = n%10;
        n /= 10;
        int b = n%10;
        if(abs(a-b)!=k)
            return false;
    }
    
    return true;
}

// function to generate all possible
// N digit number
void generateDigits(int num, int n, int k, int &count){
    if(n==0){
        if(check(num , k))
            count++;
        return;
    }
    
    for(int i=0;i<=9;i++){
        generateDigits(num*10 + i, n-1, k, count);
    }
    return;
}

// main Function
int main(){
    int n = 4, k = 2;
    int count = 0;
    for(int i=1;i<=9;i++){
        generateDigits(i, n-1, k, count);
    }
    cout << count << endl;
}

 

Output

45 

 

Complexity Analysis

Time Complexity: O(10^N)

Explanation: We are generating N digit numbers, and there can be 10^N possible N digit number, So time complexity is O(10^N).  

Space ComplexityO(1)

Explanation: No extra Space is required. 

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

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;
}

 

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 ComplexityO(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.

Previous article
Program to Find Factorial of a Large Number Recursively
Next article
Print all unique combinations of setting N objects on an NxN board
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass