Given two integers N and K, the task is to find the count of N-digit numbers such that the absolute difference of adjacent digits in the number is not greater than K.
Examples:
Input: N = 2, K = 1
Output: 26
Explanation: The numbers are 10, 11, 12, 21, 22, 23, 32, 33, 34, 43, 44, 45, 54, 55, 56, 65, 66, 67, 76, 77, 78, 87, 88, 89, 98, 99Input: N = 3, K = 2
Output: 188
Naive Approach
The simplest approach is to iterate over all N digit numbers and check for every number if the adjacent digits have an absolute difference less than or equal to K.
Time Complexity: O(10N * N)
Efficient Approach:
To optimize the above approach, we need to use a Dynamic Programming approach along with Range Update
- Initialize a DP[][] array where dp[i][j] stores the count of numbers having i digits and ending with j.
- Iterate the array from 2 to N and check if the last digit was j, then the allowed digits for this place are in the range (max(0, j-k), min(9, j+k)). Perform a range update on this range.
- Now use Prefix Sum to get the actual answer.
Below is the implementation of the above approach:
C++
// C++ implementation of// the above approach#include <bits/stdc++.h>using namespace std;// Function to return count// of N-digit numbers with// absolute difference of// adjacent digits not// exceeding Klong long getCount(int n, int k){ // For 1-digit numbers, // the count is 10 if (n == 1) return 10; long long dp[n + 1][11]; // dp[i][j] stores the number // of such i-digit numbers // ending in j for (int i = 0; i <= n; i++) { for (int j = 0; j < 11; j++) dp[i][j] = 0; } // Initialize count for // 1-digit numbers for (int i = 1; i <= 9; i++) dp[1][i] = 1; // Compute values for count of // digits greater than 1 for (int i = 2; i <= n; i++) { for (int j = 0; j <= 9; j++) { // Find the range of allowed // numbers if last digit is j int l = max(0, j - k); int r = min(9, j + k); // Perform Range update dp[i][l] += dp[i - 1][j]; dp[i][r + 1] -= dp[i - 1][j]; } // Prefix sum to find actual // values of i-digit numbers // ending in j for (int j = 1; j <= 9; j++) dp[i][j] += dp[i][j - 1]; } // Stores the final answer long long count = 0; for (int i = 0; i <= 9; i++) count += dp[n][i]; return count;}// Driver Codeint main(){ int N = 2, K = 1; cout << getCount(N, K);} |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG { // Function to return count of such numbers public static long getCount(int n, int k) { // For 1-digit numbers, the count // is 10 irrespective of K if (n == 1) return 10; // dp[i][j] stores the number // of such i-digit numbers // ending in j long dp[][] = new long[n + 1][11]; // Initialize count for // 1-digit numbers for (int i = 1; i <= 9; i++) dp[1][i] = 1; // Compute values for count of // digits greater than 1 for (int i = 2; i <= n; i++) { for (int j = 0; j <= 9; j++) { // Find the range of allowed // numbers if last digit is j int l = Math.max(0, j - k); int r = Math.min(9, j + k); // Perform Range update dp[i][l] += dp[i - 1][j]; dp[i][r + 1] -= dp[i - 1][j]; } // Prefix sum to find actual values // of i-digit numbers ending in j for (int j = 1; j <= 9; j++) dp[i][j] += dp[i][j - 1]; } // Stores the final answer long count = 0; for (int i = 0; i <= 9; i++) count += dp[n][i]; return count; } // Driver Code public static void main(String[] args) { int n = 2, k = 1; System.out.println(getCount(n, k)); }} |
Python3
# Python 3 Program to implement# the above approach# Function to return count# of N-digit numbers with # absolute difference of # adjacent digits not# exceeding Kdef getCount(n, k): # For 1-digit numbers, the # count is 10 if n == 1: return 10 # dp[i][j] stores the count of # i-digit numbers ending with j dp = [[0 for x in range(11)] for y in range(n + 1)]; # Initialize count for # 1-digit numbers for i in range(1, 10): dp[1][i]= 1 # Compute values for count # of digits greater than 1 for i in range(2, n + 1): for j in range(0, 10): # Find the range of allowed # numbers if last digit is j l = max(0, j - k) r = min(9, j + k) # Perform Range update dp[i][l] = dp[i][l] + dp[i-1][j] dp[i][r + 1] = dp[i][r + 1] - dp[i-1][j] # Prefix sum to find count of # of i-digit numbers ending with j for j in range(1, 10): dp[i][j] = dp[i][j] + dp[i][j-1] # Stores the final answer count = 0 for i in range(0, 10): count = count + dp[n][i] return count# Driver Coden, k = 2, 1print(getCount(n, k)) |
C#
// C# Program to implement// the above approachusing System;class GFG { // Function to return the // count of N-digit numbers // with absolute difference of // adjacent digits not exceeding K static long getCount(int n, int k) { // For 1-digit numbers, the // count is 10 if (n == 1) return 10; // dp[i][j] stores the count of // i-digit numbers ending with j long[, ] dp = new long[n + 1, 11]; // Initialize count for // 1-digit numbers for (int i = 1; i <= 9; i++) dp[1, i] = 1; // Compute values for count of // digits greater than 1 for (int i = 2; i <= n; i++) { for (int j = 0; j <= 9; j++) { // Find the range of allowed // numbers with last digit j int l = Math.Max(0, j - k); int r = Math.Min(9, j + k); // Perform Range update dp[i, l] += dp[i - 1, j]; dp[i, r + 1] -= dp[i - 1, j]; } // Prefix sum to count i-digit // numbers ending in j for (int j = 1; j <= 9; j++) dp[i, j] += dp[i, j - 1]; } // Stores the final answer long count = 0; for (int i = 0; i <= 9; i++) count += dp[n, i]; return count; } // Driver Code public static void Main() { int n = 2, k = 1; Console.WriteLine(getCount(n, k)); }} |
Javascript
<script>// Javascript implementation of // the above approach // Function to return count // of N-digit numbers with // absolute difference of // adjacent digits not // exceeding K function getCount(n, k){ // For 1-digit numbers, the count // is 10 irrespective of K if (n == 1) return 10; // dp[i][j] stores the number // of such i-digit numbers // ending in j var dp = new Array(n + 1); for(var i = 0; i < dp.length; i++) dp[i] = Array(11).fill(0); // Initialize count for // 1-digit numbers for(i = 1; i <= 9; i++) dp[1][i] = 1; // Compute values for count of // digits greater than 1 for(i = 2; i <= n; i++) { for(j = 0; j <= 9; j++) { // Find the range of allowed // numbers if last digit is j var l = Math.max(0, j - k); var r = Math.min(9, j + k); // Perform Range update dp[i][l] += dp[i - 1][j]; dp[i][r + 1] -= dp[i - 1][j]; } // Prefix sum to find actual values // of i-digit numbers ending in j for(j = 1; j <= 9; j++) dp[i][j] += dp[i][j - 1]; } // Stores the final answer var count = 0; for(i = 0; i <= 9; i++) count += dp[n][i]; return count;}// Driver Codevar n = 2, k = 1;document.write(getCount(n, k));// This code is contributed by umadevi9616</script> |
Output:
26
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient approach : Space optimization
In previous approach the current value DP[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D array DP of size 11 and initialize it with 0.
- Set a base case and initialize initialize count for 1 digit number dp[] = 1 .
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- Now Create a 1D array DP2 of size 11 and initialize it with 0 to store the current computation.
- Create a variable count and initialize it with 0 and get the value of count by iterate through Dp.
- At last return and print the count .
Implementation:
C++
// C++ implementation of// the above approach#include <bits/stdc++.h>using namespace std; // Function to return count// of N-digit numbers with// absolute difference of// adjacent digits not// exceeding Klong long getCount(int n, int k){ // For 1-digit numbers, // the count is 10 if (n == 1) return 10; // create DP and initialize it with 0 long long dp1[11] = {0}; // Initialize count for // 1-digit numbers for (int i = 1; i <= 9; i++) dp1[i] = 1; // iterate over subproblems ans get the current solutions for (int i = 2; i <= n; i++) { // create new DP to store current value long long dp2[11] = {0}; for (int j = 0; j <= 9; j++) { int l = max(0, j - k); int r = min(9, j + k); for (int d = l; d <= r; d++) { // update DP dp2[d] += dp1[j]; } } // assigning values to iterate further memcpy(dp1, dp2, sizeof(dp1)); } // create variable count long long count = 0; for (int i = 0; i <= 9; i++) // update count count += dp1[i]; // return final answer return count;} // Driver codeint main(){ int N = 2, K = 1; // function call cout << getCount(N, K);}// this code is contributed by bhardwajji |
Java
// Java implementation of// the above approachimport java.util.Arrays;class Main { // Function to return count// of N-digit numbers with// absolute difference of// adjacent digits not// exceeding Kstatic long getCount(int n, int k){ // For 1-digit numbers, // the count is 10 if (n == 1) return 10; // create DP and initialize it with 0 long[] dp1 = new long[11]; Arrays.fill(dp1, 0); // Initialize count for // 1-digit numbers for (int i = 1; i <= 9; i++) dp1[i] = 1; // iterate over subproblems ans get the current solutions for (int i = 2; i <= n; i++) { // create new DP to store current value long[] dp2 = new long[11]; Arrays.fill(dp2, 0); for (int j = 0; j <= 9; j++) { int l = Math.max(0, j - k); int r = Math.min(9, j + k); for (int d = l; d <= r; d++) { // update DP dp2[d] += dp1[j]; } } // assigning values to iterate further System.arraycopy(dp2, 0, dp1, 0, dp1.length); } // create variable count long count = 0; for (int i = 0; i <= 9; i++) // update count count += dp1[i]; // return final answer return count;}// Driver codepublic static void main(String[] args) { int N = 2, K = 1; // function call System.out.println(getCount(N, K));}} |
Python3
# Function to return count# of N-digit numbers with# absolute difference of# adjacent digits not# exceeding Kdef getCount(n, k): # For 1-digit numbers, # the count is 10 if n == 1: return 10 # create DP and initialize it with 0 dp1 = [0] * 11 # Initialize count for # 1-digit numbers for i in range(1, 10): dp1[i] = 1 # iterate over subproblems and get the current solutions for i in range(2, n+1): # create new DP to store current value dp2 = [0] * 11 for j in range(10): l = max(0, j - k) r = min(9, j + k) for d in range(l, r+1): # update DP dp2[d] += dp1[j] # assigning values to iterate further dp1 = dp2[:] # create variable count count = 0 for i in range(10): # update count count += dp1[i] # return final answer return count# Driver codeif __name__ == '__main__': N, K = 2, 1 # function call print(getCount(N, K)) |
Javascript
// Function to return count// of N-digit numbers with// absolute difference of// adjacent digits not// exceeding Kfunction getCount(n, k) { // For 1-digit numbers, // the count is 10 if (n == 1) { return 10; } // create DP and initialize it with 0 let dp1 = new Array(11).fill(0); // Initialize count for // 1-digit numbers for (let i = 1; i < 10; i++) { dp1[i] = 1; } // iterate over subproblems and get the current solutions for (let i = 2; i <= n; i++) { // create new DP to store current value let dp2 = new Array(11).fill(0); for (let j = 0; j < 10; j++) { let l = Math.max(0, j - k); let r = Math.min(9, j + k); for (let d = l; d <= r; d++) { // update DP dp2[d] += dp1[j]; } } // assigning values to iterate further dp1 = dp2.slice(); } // create variable count let count = 0; for (let i = 0; i < 10; i++) { // update count count += dp1[i]; } // return final answer return count;}// Driver codelet N = 2, K = 1;// function callconsole.log(getCount(N, K)); |
Output
26
Time Complexity: O(N)
Auxiliary Space: O(1) <= O(11)
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!
