Given two integers N and K, the task is to count the numbers up to N digits such that no two zeros are adjacents and the range of digits are from 0 to K-1.
Examples:
Input: N = 2, K = 3
Output: 8
Explanation:
There are 8 such numbers such that digits are from 0 to 2 only, without any adjacent 0s: {1, 2, 10, 11, 12, 20, 21, 22}Input: N = 3, K = 3
Output: 22
Approach: The idea is to use Dynamic Programming to solve this problem.
Let DP[i][j] be the number of desirable numbers up to ith digit of the number, and its last digit as j.
Observations:
- The number of ways to fill a place is
- As we know, zero’s can’t be adjacent. So when our last element is 0, means the previous index is filled by 1 way, that is 0. Therefore, current place can only be filled by (K-1) digits.
- If the last place is filled by (K-1) digits, Then current digit place can be filled by either 0 or (K-1) digits.
Base Case:
- If n == 1 and last == K, then we can fill this place by (K-1) digits, return (K-1)
- Else, return 1
Recurrence relation:
When last digit place is not filled by zero then
When Last digit place is filled by zero then
![dp[i][j] = solve(n-1, K)](data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20287%2027'%3E%3C/svg%3E "Rendered by QuickLaTeX.com")
![dp[i][j] = (K-1)*solve(n-1, K) + (K-1)*solve(n-1, 1)](https://neveropen.co.uk/wp-content/uploads/2023/11/wardslaus_quicklatex.com-9a553e917ff361d9d7526b0a9e10d191_l3-1.png "Rendered by QuickLaTeX.com")
![dp[i][j] = solve(n-1, K)](https://neveropen.co.uk/wp-content/uploads/2023/11/neveropen_quicklatex.com-f049d77e9e6e546ad9b5bda6aa73bff4_l3.png "Rendered by QuickLaTeX.com")
Below is the implementation of above approach:
C++
// C++ implementation to count the// numbers upto N digits such that// no two zeros are adjacent#include <bits/stdc++.h>using namespace std;int dp[15][10];// Function to count the// numbers upto N digits such that// no two zeros are adjacentint solve(int n, int last, int k){ // Condition to check if only // one element remains if (n == 1) { // If last element is non // zero, return K-1 if (last == k) { return (k - 1); } // If last element is 0 else { return 1; } } // Condition to check if value // calculated already if (dp[n][last]) return dp[n][last]; // If last element is non zero, // then two cases arise, // current element can be either // zero or non zero if (last == k) { // Memoize this case return dp[n][last] = (k - 1) * solve(n - 1, k, k) + (k - 1) * solve(n - 1, 1, k); } // If last is 0, then current // can only be non zero else { // Memoize and return return dp[n][last] = solve(n - 1, k, k); }}// Driver Codeint main(){ // Given N and K int n = 2, k = 3; // Function Call int x = solve(n, k, k) + solve(n, 1, k); cout << x;} |
Java
// Java implementation to count the// numbers upto N digits such that// no two zeros are adjacentimport java.io.*;public class GFG{ static int[][] dp = new int[15][10];// Function to count the numbers // upto N digits such that// no two zeros are adjacentstatic int solve(int n, int last, int k){ // Condition to check if only // one element remains if (n == 1) { // If last element is non // zero, return K-1 if (last == k) { return (k - 1); } // If last element is 0 else { return 1; } } // Condition to check if // value calculated already if (dp[n][last] == 1) return dp[n][last]; // If last element is non zero, // then two cases arise, current // element can be either zero // or non zero if (last == k) { // Memoize this case return dp[n][last] = (k - 1) * solve(n - 1, k, k) + (k - 1) * solve(n - 1, 1, k); } // If last is 0, then current // can only be non zero else { // Memoize and return return dp[n][last] = solve(n - 1, k, k); }}// Driver Codepublic static void main(String[] args){ // Given N and K int n = 2, k = 3; // Function Call int x = solve(n, k, k) + solve(n, 1, k); System.out.print(x);}}// This code is contributed by Ritik Bansal |
Python3
# Python3 implementation to count the # numbers upto N digits such that # no two zeros are adjacent dp = [[0] * 10 for j in range(15)]# Function to count the numbers# upto N digits such that no two# zeros are adjacent def solve(n, last, k): # Condition to check if only # one element remains if (n == 1): # If last element is non # zero, return K-1 if (last == k): return (k - 1) # If last element is 0 else: return 1 # Condition to check if value # calculated already if (dp[n][last]): return dp[n][last] # If last element is non zero, # then two cases arise, current # element can be either zero or # non zero if (last == k): # Memoize this case dp[n][last] = ((k - 1) * solve(n - 1, k, k) + (k - 1) * solve(n - 1, 1, k)) return dp[n][last] # If last is 0, then current # can only be non zero else: # Memoize and return dp[n][last] = solve(n - 1, k, k) return dp[n][last]# Driver code# Given N and Kn = 2k = 3# Function callx = solve(n, k, k) + solve(n, 1, k)print(x)# This code is contributed by himanshu77 |
C#
// C# implementation to count the// numbers upto N digits such that// no two zeros are adjacentusing System;class GFG{ public static int [,]dp = new int[15, 10];// Function to count the numbers // upto N digits such that// no two zeros are adjacentpublic static int solve(int n, int last, int k){ // Condition to check if only // one element remains if (n == 1) { // If last element is non // zero, return K-1 if (last == k) { return (k - 1); } // If last element is 0 else { return 1; } } // Condition to check if // value calculated already if (dp[n, last] == 1) return dp[n, last]; // If last element is non zero, // then two cases arise, current // element can be either zero // or non zero if (last == k) { // Memoize this case return dp[n, last] = (k - 1) * solve(n - 1, k, k) + (k - 1) * solve(n - 1, 1, k); } // If last is 0, then current // can only be non zero else { // Memoize and return return dp[n, last] = solve(n - 1, k, k); }}// Driver Codepublic static void Main(string[] args){ // Given N and K int n = 2, k = 3; // Function Call int x = solve(n, k, k) + solve(n, 1, k); Console.WriteLine(x);}}// This code is contributed by SoumikMondal |
Javascript
<script>// Javascript implementation to count the// numbers upto N digits such that// no two zeros are adjacentvar dp = Array.from(Array(15), () => Array(10).fill(0));// Function to count the// numbers upto N digits such that// no two zeros are adjacentfunction solve(n, last, k){ // Condition to check if only // one element remains if (n == 1) { // If last element is non // zero, return K-1 if (last == k) { return (k - 1); } // If last element is 0 else { return 1; } } // Condition to check if value // calculated already if ((dp[n][last])!=0) return dp[n][last]; // If last element is non zero, // then two cases arise, // current element can be either // zero or non zero if (last == k) { // Memoize this case return dp[n][last] = (k - 1) * solve(n - 1, k, k) + (k - 1) * solve(n - 1, 1, k); } // If last is 0, then current // can only be non zero else { // Memoize and return dp[n][last] = solve(n - 1, k, k); return dp[n][last]; }}// Driver Code// Given N and Kvar n = 2, k = 3;// Function Callvar x = solve(n, k, k) + solve(n, 1, k);document.write(x);</script> |
Output:
8
Time Complexity: O(N)
Auxiliary Space: O(N*10)
Another approach: Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a table DP to store the solution of the subproblems.
- Initialize the table with base cases
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP.
- At last return and print the final solution stored in x , where x = dp[n][k] + dp[n][1] .
Implementation :
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;int dp[15][10];// Function to count the// numbers upto N digits such that// no two zeros are adjacentint solve(int n, int k){ // Initialize the base cases for (int i = 1; i <= k; i++) { dp[1][i] = (i == k) ? (k - 1) : 1; } // Fill the table using previously computed values for (int i = 2; i <= n; i++) { for (int j = 1; j <= k; j++) { if (j == k) { dp[i][j] = (k - 1) * dp[i - 1][k] + (k - 1) * dp[i - 1][1]; } else { dp[i][j] = dp[i - 1][k]; } } } // Compute the final result int x = dp[n][k] + dp[n][1]; return x;}// Driver Codeint main(){ // Given N and K int n = 2, k = 3; // Function Call int x = solve(n, k); cout << x;}// this code contributed by bhardwajji |
Java
import java.util.*;public class Main { static int dp[][] = new int[15][10]; // Function to count the // numbers upto N digits such that // no two zeros are adjacent static int solve(int n, int k) { // Initialize the base cases for (int i = 1; i <= k; i++) { dp[1][i] = (i == k) ? (k - 1) : 1; } // Fill the table using previously computed values for (int i = 2; i <= n; i++) { for (int j = 1; j <= k; j++) { if (j == k) { dp[i][j] = (k - 1) * dp[i - 1][k] + (k - 1) * dp[i - 1][1]; } else { dp[i][j] = dp[i - 1][k]; } } } // Compute the final result int x = dp[n][k] + dp[n][1]; return x; } // Driver Code public static void main(String[] args) { // Given N and K int n = 2, k = 3; // Function Call int x = solve(n, k); System.out.println(x); }} |
Python3
# Python program for above approach# Function to count the# numbers upto N digits such that# no two zeros are adjacentdef solve(n, k): dp = [[0 for i in range(10)] for j in range(15)] # Initialize the base cases for i in range(1, k + 1): dp[1][i] = k - 1 if i == k else 1 # Fill the table using previously computed values for i in range(2, n + 1): for j in range(1, k + 1): if j == k: dp[i][j] = (k - 1) * dp[i - 1][k] + (k - 1) * dp[i - 1][1] else: dp[i][j] = dp[i - 1][k] # Compute the final result x = dp[n][k] + dp[n][1] return x# Driver Codeif __name__ == "__main__": # Given N and K n = 2 k = 3 # Function Call x = solve(n, k) print(x) |
Javascript
// JavaScript program for above approachlet dp = Array.from({length: 15}, () => Array.from({length: 10}).fill(0));// Function to count the// numbers upto N digits such that// no two zeros are adjacentfunction solve(n, k){// Initialize the base casesfor (let i = 1; i <= k; i++) {dp[1][i] = (i == k) ? (k - 1) : 1;}// Fill the table using previously computed valuesfor (let i = 2; i <= n; i++) { for (let j = 1; j <= k; j++) { if (j == k) { dp[i][j] = (k - 1) * dp[i - 1][k] + (k - 1) * dp[i - 1][1]; } else { dp[i][j] = dp[i - 1][k]; } }}// Compute the final resultlet x = dp[n][k] + dp[n][1];return x;}// Driver Codelet n = 3, k = 3;// Function Calllet x = solve(n, k);console.log(x); |
C#
// C# program for above approachusing System;class Program{static int[,] dp = new int[15, 10]; // Function to count the// numbers upto N digits such that// no two zeros are adjacentstatic int Solve(int n, int k){ // Initialize the base cases for (int i = 1; i <= k; i++) { dp[1, i] = (i == k) ? (k - 1) : 1; } // Fill the table using previously computed values for (int i = 2; i <= n; i++) { for (int j = 1; j <= k; j++) { if (j == k) { dp[i, j] = (k - 1) * dp[i - 1, k] + (k - 1) * dp[i - 1, 1]; } else { dp[i, j] = dp[i - 1, k]; } } } // Compute the final result int x = dp[n, k] + dp[n, 1]; return x;}// Driver Codestatic void Main(string[] args){ // Given N and K int n = 2, k = 3; // Function Call int x = Solve(n, k); Console.WriteLine(x);}} |
Output
8
Time Complexity: O(N*K)
Auxiliary Space: O(N*10)
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!