Approach 1: Naive approach
The naive approach to solving this problem is to generate all possible N-digit numbers and count those that satisfy the above condition. This is not an efficient approach as we need to iterate all possible N-digit numbers.
Time complexity
O(N * 10^N), where ‘N’ is the count of digits present in the number.
Space complexity
O(1), constant space as we didn’t use any extra space except a few variables.
Approach 2: Dynamic Programming Approach
In this approach, we will discuss how we can reach our result using dynamic programming. All the subproblems stored in 3-dimensional array, i.e., DP[][][]. Here, we use the memoization method. The idea is to build a number from left to right by placing all single-digit numbers in all positions. Keep track of the previously filled digit and if the number is continuously filled more than the given times then not take that number. Let's discuss the algorithm as follows:
Algorithm
-
The first position can have any digit.
-
Keep track of previously filled digit from the second position and the count up to which that number can appear continuously.
-
Decrement the count of digit if the previously filled digit is the same and if the count is zero then ignore that digit in the next recursive call.
- At each of the above recursive calls when the resultant number is generated then increment the count for that number.
Program
// Count all possible N-digit numbers such that each digit does not appear more than the given number of times consecutively
#include <iostream>
#include <cstring>
using namespace std;
// Globally declare DP array.
int dp[1000][10][10];
int getCount(int N, int maxDigit[], int pos, int prev, int count)
{
// Base Condition to terminate the recursive call.
if (pos == N)
{
return 1;
}
// Check if DP[pos][prev][count] is already computed or not.
if (dp[pos][prev][count] != -1)
{
return dp[pos][prev][count];
}
// Initialize DP[pos][prev][count] as zero
dp[pos][prev][count] = 0;
for (int i = 0; i <= 9; ++i)
{
// Check if the previous value is 'i' or not.
if (count == 0 && prev != i)
{
dp[pos][prev][count] += (getCount(N, maxDigit, pos + 1, i, maxDigit[i] - 1));
}
else if (count != 0)
{
dp[pos][prev][count] += (getCount(N, maxDigit, pos + 1, i, (prev == i && pos != 0) ? count - 1 : maxDigit[i] - 1));
}
}
// Return ans.
return dp[pos][prev][count];
}
// Function to get our result.
void getResult(int N, int maxDigit[])
{
// Stores the final answer
int result = getCount(N, maxDigit, 0, 0, 1);
// Print the answer.
cout << result;
}
// Driver Code
int main()
{
// Taking Number of digits as input.
int N;
cin >> N;
int maxDigit[10];
for (int i = 0; i < 10; i++)
{
cin >> maxDigit[i];
}
// Initialize the dp array with -1
memset(dp, -1, sizeof(dp));
// Function call for getting the result.
getResult(N, maxDigit);
return 0;
}
You can also try this code with Online C++ Compiler
Input
2
2 1 1 1 1 1 1 1 1 1
You can also try this code with Online C++ Compiler
Output
91
You can also try this code with Online C++ Compiler
Time Complexity
O(N*10*10), where ‘N’ is the given number.
As in each recursive call, all the digits have been checked.
Space Complexity
O(N*10*10), where ‘N’ is the given number.
As we are creating a ‘DP’ array of size N*10*10.
Check out Longest Common Substring
Frequently Asked Questions
What are states in dynamic programming?
The states of DP are minor issues inside the larger problem. Each state represents a subset of the input data that was used to get the final result for the entire problem input.
What is recursion?
In programming, recursion occurs when a function, known as a recursive function, calls itself directly or indirectly based on particular criteria.
In terms of language, what is recursion?
The phenomenon of repeating things in a way that appears similar to the parent object is known as recursion in language.
What is the base case?
The precalculated value for the smaller situations is the basic case. It's utilised to bring the recursive calls to a close.
What is the purpose of recursion?
Recursion is a technique for breaking down a complicated task into smaller task.
Conclusion
In this blog, we have learned two approaches to solve the problem Count all possible N-digit numbers such that each digit does not appear more than the given number of times consecutively. The first approach is the brute force approach. Brute forces are always the first to go. We also discussed how to optimize the first approach to reduce the time complexity by using Dynamic Programming.
Also check out - Rod Cutting Proble
If you want to explore more then head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!
7+ registered 
