Thursday, February 9, 2023
HomeSoftware DevelopmentRely methods to generate N digit quantity such that its each digit...

# Rely methods to generate N digit quantity such that its each digit divisible by earlier digit

Given a quantity N, the duty is to rely the variety of methods to create an N digit quantity from digits 1 to 9 such that each digit is divisible by its earlier digit that’s if the quantity is represented by an array of digits A then A[i + 1] % A[i] == 0. print the reply modulo 109 + 7.

Examples:

Enter: N = 2
Output: 23
Rationalization: For N = 2 potential solutions are 11, 12, 13, 14, 15, 16, 17, 18, 19, 22, 24, 26, 28, 33, 36, 39, 44, 48, 55, 66, 77, 88, and 99.

Enter: N = 3
Output:  44

Naive method: The fundamental technique to clear up the issue is as follows:

The fundamental technique to clear up this drawback is to generate all potential combos by utilizing a recursive method.

Time Complexity: O(9N)
Auxiliary Area: O(1)

Environment friendly Method:  The above method might be optimized based mostly on the next thought:

Dynamic programming can be utilized to resolve this drawback

• dp[i][j] represents the variety of methods of making numerous dimension i and j is its earlier digit taken.
• It may be noticed that the recursive perform known as exponential instances. That implies that some states are known as repeatedly.
• So the concept is to retailer the worth of every state. This may be carried out by storing the worth of a state and every time the perform known as, returning the saved worth with out computing once more.

Observe the steps under to resolve the issue:

• Create a recursive perform that takes two parameters representing ith place to be stuffed and j representing the final digit taken.
• Name the recursive perform for selecting all digits from 1 to 9.
• Base case if all positions stuffed return 1.
• Create a second array of dp[N] initially full of -1.
• If the reply for a specific state is computed then put it aside in dp[i][j].
• If the reply for a specific state is already computed then simply return dp[i][j].

Under is the implementation of the above method:

## C++

 `#embody ` `utilizing` `namespace` `std;` ` `  `const` `int` `MOD = 1e9 + 7;` ` `  `int` `dp;` ` `  `int` `recur(``int` `i, ``int` `j, ``int` `N)` `{` ` `  `    ` `    ``if` `(i == N) {` `        ``return` `1;` `    ``}` ` `  `    ` `    ` `    ` `    ``if` `(dp[i][j] != -1)` `        ``return` `dp[i][j];` ` `  `    ` `    ``int` `ans = 0;` ` `  `    ` `    ``if` `(i == 0) {` ` `  `        ` `        ` `        ``for` `(``int` `digit = 1; digit <= 9; digit++) {` ` `  `            ` `            ` `            ``ans = (ans + recur(i + 1, digit, N)) % MOD;` `        ``}` `    ``}` ` `  `    ` `    ` `    ``else` `{` ` `  `        ` `        ` `        ``for` `(``int` `digit = 1; digit <= 9; digit++) {` ` `  `            ` `            ` `            ` `            ``if` `(digit % j == 0)` `                ``ans = (ans + recur(i + 1, digit, N)) % MOD;` `        ``}` `    ``}` ` `  `    ` `    ``return` `dp[i][j] = ans;` `}` ` `  `int` `countWays(``int` `N)` `{` ` `  `    ` `    ``memset``(dp, -1, ``sizeof``(dp));` ` `  `    ` `    ` `    ``int` `ans = recur(0, 0, N);` ` `  `    ` `    ``return` `ans;` `}` ` `  `int` `major()` `{` ` `  `    ` `    ``int` `N = 2;` ` `  `    ` `    ``cout << countWays(N) << endl;` ` `  `    ` `    ``int` `N1 = 3;` ` `  `    ` `    ``cout << countWays(N1) << endl;` `    ``return` `0;` `}`

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

Associated Articles:

RELATED ARTICLES