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

Brute Force Approach

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

Algorithm

1. A boolean function “mean” is defined that takes integer N. 
    
2. Initialize an array “digits” inside “mean” to store the digits of the input integer.
    
3. Using a while loop stores the digits in the array “digits”.
    
4. Now iterate through the “digits” array from second to the second last digit.
    
5. Now, check inside the for loop if each digit is equal to the mean of the neighbouring digits and return true or false depending on the output.
    
6. Now, in the “count” function use a for loop to iterate over all integers with N digits(i.e., between 10^(N-1) and 10^N - 1, inclusive).
    
7. Increment the ‘cnt’ if the “mean” function is satisfied. 
    
8. Finally, return the value of count.

Dry Run 

1. For the input N=1, the “count” function returns the count of N-digit numbers,where each digit is the mean of its two adjacent digits.
    
2. Using a for loop, iterate over all ‘N’ digit numbers between 10^(N-1) and 10^N - 1 i.e., between 0 to 9.
    
3. For each i the “mean” function is called to check if the number satisfies the "mean" property.
    
4. If the “mean” function returns true, then the “cnt” is incremented.

 5. Finally return the ‘cnt’ which is 10 in this case.

Code in C++ 

#include <bits/stdc++.h>

using namespace std;

// Function to check if number is a mean number
bool mean(int N) {
    // Initialize an array
    int digits[10];
    int i = 0;
    
    // Store the elements in array
    while (N > 0) {
        digits[i] = N % 10;
        i++;
        N /= 10;
    }
    
    /*
        Check if the digits of the 
        number satisfy the mean property
    */
    for (int j = 1; j < i - 1; j++) {
        if (digits[j] != (digits[j-1] + digits[j+1]) / 2) {
            return false;
        }
    }
    return true;
}

int count(int N) {
    int cnt = 0;
    // Iterate through all N digit numbers 
    for (int i = pow(10, N-1); i < pow(10, N); i++) {
        // If "mean" is true, increment count
        if (mean(i)) {
            cnt++;
        }
    }
    
    // If N == 1 then, 0 is also added
    if(N == 1){
        return cnt+1;
    }
    
    // Else return count
    else{
        return cnt;
    }
}

int main() {
    int N = 1;
    // Call the function and print the result  
    cout << count(N) << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Complexity

Time Complexity = O(N * 10^N)

The overall time complexity is O(N * 10^N), where N is the complexity is the length of the sequence.

Space Complexity = O(log N)

We are implementing an array which takes O(log N) space. Therefore the space complexity is O(log N)

Dynamic Programming 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 satisfy the conditions. Now consider a three-digit number D. Let d1, d2, and d3 be the digits in the decimal representation of D. If D has to satisfy the condition then,

Now, if we want to add one more digit, d4 to D, to make it a four-digit number such that it satisfies the condition of counting numbers having each digit as the mean of the adjacent digits then,

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

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

1. Declare a three-dimensional array dp[101][11][11] to store each state.
    
2. Now call a recursive function solve() that takes inputs: ind (current index), P1 (previous digit), P2 (second previous digit), and N (total number of digits).
    
3. Check for the base condition where ind == N + 1. If this condition is met, return 1.
    
4. Check if the state (ind, P1, P2) has already been computed. If yes, return the dp[ind][P1][P2].
    
5. If the state has not been computed, set dp[ind][P1][P2] to 0.
    
6. If ‘ind’ is 1, set the range for ‘st’ and ‘en’ from 1 to 9, and if N is 1, set ‘st’ to 0. Iterate over the range of ‘st’ to ‘en’ and for each value ‘st’, add the result of the recursive call solve(ind + 1, st, P1, N) to dp[ind][P1][P2].
    
7. If ‘ind’ is 2, iterate over the range of digits from 0 to 9 and for each value ‘i’, add the result of the recursive call solve(ind + 1, i, P1, N) to dp[ind][P1][P2].
    
8. If ‘ind’ is greater than 2, try to place the digit 2 * P1 - P2 and 2 * P1 - P2 + 1. 
    
9. If 2 * P1 - P2 is in the range [0, 9], add the result of the recursive call solve(ind + 1, 2 * P1 - P2, P1, N) to dp[ind][P1][P2]. 
    
10. If 2 * P1 - P2 + 1 is in the range [0, 9], add the result of the recursive call solve(ind + 1, 2 * P1 - P2 + 1, P1, N) to dp[ind][P1][P2].
     
11. Return the value of dp[ind][P1][P2].

Dry Run

1. We are given N = 1. 
    
2. Initialize the dp array with -1.
    
3. Now we call the function solve(1, 0, 0, N) which takes four arguments.
   • ind = 1 : it is the current position in the sequence.
      
   • P1 = 0 : it represents the value of the previous digit.
      
   • P2 = 0 : it represents the value of the digit before the previous digit.
      
   • N = 1 : it is the length of the sequence.
      
4. Now we will analyse how solve() function works for every value of ind.

 5. For ind = 1.

• The loop iterates from i = 0(since value of N is 1) to i = 9 and for each digit solve() function is called recursively with solve(ind+1, st, P1, N).
   
• For every value of i from 0 to 9, 1 will be added to dp[ind][P1][P2].
   
• Since this is the first digit and there are 10 values in the range. Therefore, dp[ind][P1][P2] becomes 10 after the loop ends.
   

 6. Finally the answer is returned as 10.

Code in C++

#include <bits/stdc++.h>
using namespace std;

// Three dimensional matrix to memorize each state
int dp[101][11][11]; 

// Recursive function that compute the answer for states (ind, P1, P2, N)
int solve(int ind, int P1, int P2, int N){ 
    // Base Case
    if(ind == N + 1)             
        return 1;
        
    // If the state has already been computed
    if(dp[ind][P1][P2] != -1)    
        return dp[ind][P1][P2];

    dp[ind][P1][P2] = 0;

    if(ind == 1){
        // We can place any digit from [1, 9]
        int st = 1, en = 9; 
        
        // But if N == 1, 0 can also be placed
        if(N == 1)              
            st = 0;  

        for(st; st <= en; ++st){
            dp[ind][P1][P2] += solve(ind + 1, st, P1, N);
        }    
    
    }
    
    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, N);
        }    
    }
    
    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, N);

        // 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, N);
    }

    // Return ans
    return dp[ind][P1][P2];
}

int main(){
    int N = 1;
    // Initializing dp table with -1 
    memset(dp, -1, sizeof(dp));

    // Function call
    cout << solve(1, 0, 0, N) << "\n";

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Complexity

Time Complexity = O(N * 10 * 10)

The overall time complexity is O(N * 10 * 10) where ‘N’ is the length of the sequence. This is because there are ‘N’ possible states of the index.

Space Complexity = O(N * 10 * 10)

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

Check out Longest Common Substring

Frequently Asked Questions

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.  

What is a base case?  

A base case is the precalculated value for the smaller cases. It is used to terminate the recursive calls.

What is memoization?

Memoization is a technique to optimize the recursive solution. It ensures that each state does not execute more than once. 

What is a top down approach in dynamic programming?

In the top-down approach the problem is divided into subproblems, and the solutions to subproblems are stored. 

What is a bottom up approach in dynamic programming?

In the bottom-up solutions to subproblems are computed iteratively and stored in a table until the solution to the original problem is computed.

Conclusion

In this blog, we learned the problem of finding the count of N digit numbers having each digit as the mean of its adjacent digits.. We have implemented the problem in C++ programming language starting from a naive approach to the most optimized approach.

For more string data structure articles, you can refer following links:

• Count of N-digit Numbers whose bitwise AND Of Adjacent Digits Equals 0
• Total count of sorted numbers up to N digits in the range [L, R]
• Count Number of Valid Parenthesis
   

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enrol in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!