Given two integers N and K. The task is to count all positive integers with length N having an absolute difference between adjacent digits equal to K.
Examples:
Input: N = 4, K = 8
Output: 3
Explanation: The absolute difference between every consecutive digit of each number is 8. Three possible numbers are 8080, 1919 and 9191.Input: N = 2, K = 0
Output: 9
Explanation: 11, 22, 33, 44, 55, 66, 77, 88, 99. The absolute difference between every consecutive digit of each number is 0.
Â
Approach: The approach is based on recursion. Iterate over digits [1, 9], and for each digit, count the N-digit number having a difference of absolute digit as K using recursion. Following cases arrive in the recursive function call.
- Base Case: For all single-digit integers i.e. N = 1, increment answer count.
- Recursive Call: If adding digit K to the one’s digit of the number formed till now (num) does not exceed 9, then recursively call by decreasing N and making num = (num*10 + num%10 + K).
if(num % 10 + K ≤ 9)Â
  recursive_function(10 * num + (num % 10 + K), N – 1);Â
- If the value of K is non-zero after all the recursive calls and if num % 10 ≥ K, then again recursively call by decreasing the N and update num to (10*num + num%10 – K).
if(num % 10 ≥ K)Â
  recursive_function(10 * num + num % 10 – K, N – 1)
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;Â
// To store the count of numbersint countNums = 0;Â
// Function that recursively finds the// possible numbers and append into ansvoid checkUtil(int num, int K, int N){    // Base Case    if (N == 1) {        countNums++;        return;    }Â
    // Check the sum of last digit and k    // less than or equal to 9 or not    if ((num % 10 + K) <= 9)        checkUtil(10 * num +                   (num % 10 + K), K, N - 1);Â
    // If K = 0, then subtraction and    // addition does not make any    // difference    if (K) {                 // If unit's digit greater than K        if ((num % 10 - K) >= 0)            checkUtil(10 * num +                      num % 10 - K, K, N - 1);    }}Â
// Function to call checkUtil function// for every integer from 1 to 9void check(int K, int N){    // Loop to check for     // all digits from 1 to 9    for (int i = 1; i <= 9; i++) {        checkUtil(i, K, N);    }}Â
// Driver Codeint main(){Â Â Â Â // Given N and KÂ Â Â Â int N = 4, K = 8;Â Â Â Â check(K, N);Â
    // Count total possible numbers    cout << countNums << endl;    return 0;} |
Java
// Java program for the above approachimport java.util.*;Â
class GFG{Â
// To store the count of numbersstatic int countNums = 0;Â
// Function that recursively finds the// possible numbers and append into ansstatic void checkUtil(int num, int K, int N){       // Base Case    if (N == 1) {        countNums++;        return;    }Â
    // Check the sum of last digit and k    // less than or equal to 9 or not    if ((num % 10 + K) <= 9)        checkUtil(10 * num +                   (num % 10 + K), K, N - 1);Â
    // If K = 0, then subtraction and    // addition does not make any    // difference    if (K>0) {                 // If unit's digit greater than K        if ((num % 10 - K) >= 0)            checkUtil(10 * num +                      num % 10 - K, K, N - 1);    }}Â
// Function to call checkUtil function// for every integer from 1 to 9static void check(int K, int N){       // Loop to check for     // all digits from 1 to 9    for (int i = 1; i <= 9; i++) {        checkUtil(i, K, N);    }}Â
// Driver Codepublic static void main(String[] args){Â Â Â Â Â Â Â // Given N and KÂ Â Â Â int N = 4, K = 8;Â Â Â Â check(K, N);Â
    // Count total possible numbers    System.out.print(countNums +"\n");}}Â
// This code contributed by shikhasingrajput |
Python3
# Python program for the above approachÂ
# To store the count of numberscountNums = 0;Â
# Function that recursively finds the# possible numbers and append into ansdef checkUtil(num, K, N):    global countNums;         # Base Case    if (N == 1):        countNums += 1;        return;Â
    # Check the sum of last digit and k    # less than or equal to 9 or not    if ((num % 10 + K) <= 9):        checkUtil(10 * num + (num % 10 + K), K, N - 1);Â
    # If K = 0, then subtraction and    # addition does not make any    # difference    if (K > 0):Â
        # If unit's digit greater than K        if ((num % 10 - K) >= 0):            checkUtil(10 * num + num % 10 - K, K, N - 1);Â
# Function to call checkUtil function# for every integer from 1 to 9def check(K, N):       # Loop to check for    # all digits from 1 to 9    for i in range(1,10):        checkUtil(i, K, N);Â
# Driver Codeif __name__ == '__main__':Â Â Â Â # Given N and KÂ Â Â Â N = 4;Â Â Â Â K = 8;Â Â Â Â check(K, N);Â
    # Count total possible numbers    print(countNums);Â
# This code is contributed by shikhasingrajput |
C#
// C# program for the above approachusing System;Â
class GFG{Â
// To store the count of numbersstatic int countNums = 0;Â
// Function that recursively finds the// possible numbers and append into ansstatic void checkUtil(int num, int K, int N){         // Base Case    if (N == 1)    {        countNums++;        return;    }Â
    // Check the sum of last digit and k    // less than or equal to 9 or not    if ((num % 10 + K) <= 9)        checkUtil(10 * num +                  (num % 10 + K), K, N - 1);Â
    // If K = 0, then subtraction and    // addition does not make any    // difference    if (K > 0)     {                 // If unit's digit greater than K        if ((num % 10 - K) >= 0)            checkUtil(10 * num +                      num % 10 - K, K, N - 1);    }}Â
// Function to call checkUtil function// for every integer from 1 to 9static void check(int K, int N){         // Loop to check for     // all digits from 1 to 9    for(int i = 1; i <= 9; i++)     {        checkUtil(i, K, N);    }}Â
// Driver Codepublic static void Main(String[] args){Â Â Â Â Â Â Â Â Â // Given N and KÂ Â Â Â int N = 4, K = 8;Â Â Â Â check(K, N);Â
    // Count total possible numbers    Console.Write(countNums + "\n");}}Â
// This code is contributed by 29AjayKumar |
Javascript
<script>Â Â Â Â Â Â // JavaScript code for the above approachÂ
      // To store the count of numbers      let countNums = 0;Â
      // Function that recursively finds the      // possible numbers and append into ans      function checkUtil(num, K, N)       {                 // Base Case          if (N == 1) {              countNums++;              return;          }Â
          // Check the sum of last digit and k          // less than or equal to 9 or not          if ((num % 10 + K) <= 9)              checkUtil(10 * num +                  (num % 10 + K), K, N - 1);Â
          // If K = 0, then subtraction and          // addition does not make any          // difference          if (K) {Â
              // If unit's digit greater than K              if ((num % 10 - K) >= 0)                  checkUtil(10 * num +                      num % 10 - K, K, N - 1);          }      }Â
      // Function to call checkUtil function      // for every integer from 1 to 9      function check(K, N)       {                 // Loop to check for           // all digits from 1 to 9          for (let i = 1; i <= 9; i++) {              checkUtil(i, K, N);          }      }Â
      // Driver CodeÂ
      // Given N and K      let N = 4, K = 8;      check(K, N);Â
      // Count total possible numbers      document.write(countNums + '<br>');Â
// This code is contributed by Potta Lokesh  </script> |
Output
3
Time Complexity: O(2N)
Auxiliary Space: O(1)
Â
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
