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!
