Count of N Digit Numbers having each Digit as the Mean of its Adjacent Digits

Abhishek Ranjan
Last Updated: May 13, 2022

Problem Statement

 

You have an integer N. Your task is to find the number of N-digit numbers, which are good.

A number is called good if each digit in its decimal representation is the mean of its two adjacent digits.

For example:

  • 9 is a good number: there is only one digit in 9. So it satisfies all the constraints.  
  • 10 is a good number: there is no digit having two neighbours.
  • 102 is not a good number: 0 is not the mean of its two neighbours, 1 and 2.                                                                                    

Constraints

 

1 <= N <= 1000

 

Sample Test Cases

 

Input 1:
1
Output 1: 
10
Explanation: All the numbers from 1 to 9 are good because there is only one digit, so they satisfy all the constraints.

Input 2:
2
Output 2:
90

Input 3:
3
Output 3:
90

Approach

 

Brute Force Solution

The most straightforward approach is to iterate over all the N-digits numbers and check which satisfies all the constraints and keep their count. 

Also, to reduce the number of operations, we can recursively generate all the N-digits numbers and terminate the recursive calls whenever we encounter a digit that does not satisfy the constraints.

The worst-case time complexity of both approaches is O(N * 10^N). Hence both approaches are inefficient.

 

Efficient Approach

We can solve the problem efficiently by using Dynamic Programming.

Let's try to find out the subproblems (states of DP).

We know that all the two-digit and one-digit numbers are good. Now consider a three-digit number D. Let d1,d2, and d3 be the digits in the decimal representation of D.

If D is good number then,

 

					d2 = (d1 + d3)/2
Or,                 d2 = (d1 + d3 - 1)/2                 (mean involves integer division)
				    d3 = 2 * d2 - d1- 1 or d3 = 2 * d2 - d1 + 1

 

Now, if we want to add one more digit, d4 to D, to make it a four-digit good number then,

 

					d4 = 2 * d3 - d2 - 1 or d4 = 2 * d3 - d2 + 1

 

In general, if we want to add the Kth digit to a sequence then,

 

					d[k] = 2 * d[k - 1] - d[k - 2]
					Or, d[k] = 2 * d[k - 1] - d[k - 2] + 1

 

So, if we want to add a digit at a particular index ind, then we need the digit at the previous two indices. Let P1 be the previous digit, and P2 be the second previous selected digit. So the states of the DP are (ind, P1, P2).  It gives the answer from index ind till the end when the previously selected digits are P1 and P2.

It can be seen that there are overlapping subproblems. So we can use a three-dimensional matrix dp[ind][P1][P2] to memorize each state.

 

Algorithm

  • Define a recursive function solve(ind, P1, P2), which computes the answer for the state (ind, P1, P2).
  • If ind == N + 1 we can return 1 as a N-digit good number is formed. 
  • If the current index ind is 1, then we can place any digit from [1, 9]. But if N = 1, we can add 0 also.
  • If the current index ind is 2, we can place any digit from [0, 9].
  • If the current index ind is greater than 2, then we can place (2 * P1 - P2) if 0 <= (2 * P1 - P2) <= 9.
  • Similarly, we can also place (2 * P1 - P2 + 1) if 0 <= (2 * P1 - P2 + 1) <= 9.

Code

 

#include <bits/stdc++.h>
using namespace std;
int dp[101][11][11]; //three dimentional matrix to memorize each state
int N; //Given input

//recursive function that compute the answer for states (ind, P1, P2)
int solve(int ind, int P1, int P2){ 
   
   if(ind == N + 1)             //Base Case
       return 1;
   if(dp[ind][P1][P2] != -1)    //if the state has already been computed
       return dp[ind][P1][P2];
   dp[ind][P1][P2] = 0;
   if(ind == 1){
       int st = 1, en = 9;     //we can place any digit from [1, 9]
       if(N == 1)              //but if N == 1, 0 can also be placed
           st = 0;  
       for(st; st <= en; ++st){
           dp[ind][P1][P2] += solve(ind + 1, st, P1);
       }    
   
   }
   else if(ind == 2){
       
       //place any digit from [0, 9]
       for(int i = 0; i <= 9; i++){
           dp[ind][P1][P2] += solve(ind + 1, i, P1);
       }
   
   }
   else{
       
       //try to place (2 * P1 - P2)
       if(2 * P1 - P2 <= 9 and 2 * P1 - P2 >= 0)
           dp[ind][P1][P2] += solve(ind + 1, 2 * P1 - P2, P1);
       //try to place (2 * P1 - P2 + 1)
       if(2 * P1 - P2 + 1 <= 9 and 2 * P1 - P2 + 1 >= 0)
           dp[ind][P1][P2] += solve(ind + 1, 2 * P1 - P2 + 1, P1);
   
   }
   //return ans
   return dp[ind][P1][P2];
}
int main(){
   //Given Input
   cin >> N;
   //intializing dp table with -1 
   memset(dp, -1, sizeof(dp));
   //function call
   cout << solve(1, 0, 0) << "\n";
   return 0;
}

 

Time Complexity

 

The overall time complexity is O(N * 10 * 10).

Space Complexity

 

We need a 3D array of size (N * 10 * 10) to memorize each state. So the overall space complexity is O(N * 10 * 10).

 

FAQs

  1. What are states in dynamic programming?    
    The states of DP are the subproblems to the more significant problem. Each state is a subset of the input data used to build the result for the whole problem input.  
     
  2. What is the base case?  
    The base case is the precalculated value for the smaller cases. It is used to terminate the recursive calls.
     
  3. What is memoization?
    Memoization is a technique to optimize the recursive solution. It ensure that each state does not execute more than once. 

Key Takeaways

 

In this article, we tried to solve a problem using dynamic programming. Having a good hold on Dynamic Programming is very important for cracking coding interviews at MAANG. 

Check out the coding ninjas master class on dynamic programming for getting a better hold on it.

To learn more about such data structures and algorithms, Codestudio is a one-stop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various product-based companies by providing Online Mock Test Series and many more benefits.

Happy learning!

 

 

 

 

Was this article helpful ?
0 upvotes