Dynamic programming has always been one of the hot topics in the interviews. Here, we will discuss one of the problems that can be solved using dynamic programming.

So why to wait? Let’s deep dive into the solution.

Problem Statement

You have an integer N. Your task is to find the number of N-digit numbers,where each digit is the mean of its two adjacent digits and N should be in the range of 1 <= N <= 1000.

Example

Input

1 3

Output

10 90

Explanation

All the numbers from 0 to 9 can be represented as the mean of its two adjacent digits because there is only one digit, so they satisfy all the constraints. There are 90 numbers between 100 to 999(both inclusive) that can be represented as the mean of its two adjacent digits.

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

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

A boolean function “mean” is defined that takes integer N.

Initialize an array “digits” inside “mean” to store the digits of the input integer.

Using a while loop stores the digits in the array “digits”.

Now iterate through the “digits” array from second to the second last digit.

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.

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).

Increment the ‘cnt’ if the “mean” function is satisfied.

Finally, return the value of count.

Dry Run

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.

Using a for loop, iterate over all ‘N’ digit numbers between 10^(N-1) and 10^N - 1 i.e., between 0 to 9.

For each i the “mean” function is called to check if the number satisfies the "mean" property.

If the “mean” function returns true, then the “cnt” is incremented.

Value of i

Previous Digit

Next Digit

Mean of adjacent digits

cnt

0

-1

1

0

1

1

0

2

1

2

2

1

3

2

3

3

2

4

3

4

4

3

5

4

5

5

4

6

5

6

6

5

7

6

7

7

6

8

7

8

8

7

9

8

9

9

8

10

9

10

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

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

Declare a three-dimensional array dp[101][11][11] to store each state.

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).

Check for the base condition where ind == N + 1. If this condition is met, return 1.

Check if the state (ind, P1, P2) has already been computed. If yes, return the dp[ind][P1][P2].

If the state has not been computed, set dp[ind][P1][P2] to 0.

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].

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].

If ‘ind’ is greater than 2, try to place the digit 2 * P1 - P2 and 2 * P1 - P2 + 1.

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].

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].

Return the value of dp[ind][P1][P2].

Dry Run

We are given N = 1.

Initialize the dp array with -1.

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.

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

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).

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: