## 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

- Generate all possible N digits numbers using recursion
- Check for each N digit number formed if the absolute difference between adjacent digits is equal to k.
- If The number satisfies the condition, increase the count.
- 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 Complexity**: **O(1)**

Explanation: No extra Space is required.