Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
The Problem Statement
2.1.
Explanation
3.
Approach 1: Naive approach
3.1.
Time complexity
3.2.
Space complexity
4.
Approach 2: Dynamic Programming Approach
4.1.
Algorithm
4.2.
Program
4.2.1.
Input
4.2.2.
Output
4.3.
Time Complexity
4.4.
Space Complexity
5.
Frequently Asked Questions
5.1.
What are states in dynamic programming?
5.2.
What is recursion?
5.3.
In terms of language, what is recursion?
5.4.
What is the base case?
5.5.
What is the purpose of recursion?
6.
Conclusion
Last Updated: Mar 27, 2024

Count All Possible N-digit Numbers Such that Each Digit Does Not Appear More Than the Given Number of Times Consecutively

Author Ujjawal Gupta
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

In this blog, we will discuss a problem based on dynamic programming in which we have to find the count of all N-digit numbers such that each digit does not appear more than the given number of times consecutively.  Dynamic Programming based coding problems is widely asked in competitive programming contests and various coding interviews. Here we will discuss the approach based on dynamic programming.

The Problem Statement

Suppose you are given an integer ‘N’ and an array ‘ARR’ of size 10, where each index stores an integer denoting the maximum number of times that digit appears consecutively. Your task is to find the count of all possible N-digits numbers such that each digit does not occur more than the given number of times sequentially. 

Explanation

Let us understand the above problem with the help of an example:

Let N = 2 and ARR = {2, 1, 1, 1, 1, 1, 1, 1, 1, 2}.

Here, numbers {11, 22, 33, 44, 55, 66, 77, 88} are not valid.

Hence, total count is all possible N-digit numbers - 8 = 100 - 8 = 92.

Therefore, all possible N-digit numbers that consecutively don’t appear more than once except 0 and 9 are 92.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

Input

2
2 1 1 1 1 1 1 1 1 1

Output

91

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!

Previous article
Count of N Digit Numbers having each Digit as the Mean of its Adjacent Digits
Next article
Nth Number
Live masterclass