Count ways to create N digit number with adjacent digits different and number is divisible by 3

Given integer N, the task is to count the number of ways( modulo 10⁹ + 7) to create an N digit number from digits 1 to 9 such that adjacent digits are different and the number is divisible by 3.

Examples: 

Input: N = 1
Output: 3
Explanation: 3, 6, and 9 are the only possible numbers.

Input: N = 2
Output:  24
Explanation: 12, 15, 18, 21, 24, 27, 36, 39, 42, 45, 48, 51, 54, 57, 63, 69, 72, 75, 78, 81, 84, 87, 93,  and 96 are possible numbers. 

Naive approach: The basic way to solve the problem is as follows:

The basic way to solve this problem is to generate all possible combinations by using a recursive approach.

Time Complexity: O(8^N)
Auxiliary Space: O(1)

Efficient Approach:  The above approach can be optimized based on the following idea:

Dynamic programming can be used to solve this problem

• By divisibility test of 3: it’s enough to keep track of the (sum of digits % 3) if its zero then number is divisible by 3.
• dp[i][j][k] represents the number of ways of creating number with size i digits,   j last number picked and k is sum of digits picked modulo 3. 

It can be observed that the recursive function is called exponential times. That means that some states are called repeatedly. So the idea is to store the value of each state. This can be done using by the store the value of a state and whenever the function is called, returning the stored value without computing again.

Follow the steps below to solve the problem:

• Create a recursive function that takes three parameters i representing i’th position of number that has to be filled with a digit, j representing the previous digit picked, and k representing the sum of digits modulo 3. 
• Call the recursive function for choosing all digits from 1 to 9.
• Base case if the number is formed with N digits and j is zero then return 1 else return 0.
• Create a 3d array of dp[N][11][3] initially filled with -1.
• If the answer for a particular state is computed then save it in dp[i][j][k].
• If the answer for a particular state is already computed then just return dp[i][j][k].

Below is the implementation of the above approach:

Time Complexity: O(N)
Auxiliary Space: O(N)

Related Articles:

Given integer N, the task is to count the number of ways( modulo 10⁹ + 7) to create an N digit number from digits 1 to 9 such that adjacent digits are different and the number is divisible by 3.

Examples: 

Input: N = 1
Output: 3
Explanation: 3, 6, and 9 are the only possible numbers.

Input: N = 2
Output:  24
Explanation: 12, 15, 18, 21, 24, 27, 36, 39, 42, 45, 48, 51, 54, 57, 63, 69, 72, 75, 78, 81, 84, 87, 93,  and 96 are possible numbers. 

Naive approach: The basic way to solve the problem is as follows:

The basic way to solve this problem is to generate all possible combinations by using a recursive approach.

Time Complexity: O(8^N)
Auxiliary Space: O(1)

Efficient Approach:  The above approach can be optimized based on the following idea:

Dynamic programming can be used to solve this problem

• By divisibility test of 3: it’s enough to keep track of the (sum of digits % 3) if its zero then number is divisible by 3.
• dp[i][j][k] represents the number of ways of creating number with size i digits,   j last number picked and k is sum of digits picked modulo 3. 

It can be observed that the recursive function is called exponential times. That means that some states are called repeatedly. So the idea is to store the value of each state. This can be done using by the store the value of a state and whenever the function is called, returning the stored value without computing again.

Follow the steps below to solve the problem:

• Create a recursive function that takes three parameters i representing i’th position of number that has to be filled with a digit, j representing the previous digit picked, and k representing the sum of digits modulo 3. 
• Call the recursive function for choosing all digits from 1 to 9.
• Base case if the number is formed with N digits and j is zero then return 1 else return 0.
• Create a 3d array of dp[N][11][3] initially filled with -1.
• If the answer for a particular state is computed then save it in dp[i][j][k].
• If the answer for a particular state is already computed then just return dp[i][j][k].

Below is the implementation of the above approach:

Time Complexity: O(N)
Auxiliary Space: O(N)

Related Articles: