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][10] 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 <bits/stdc++.h>

utilizing namespace std;

  

const int MOD = 1e9 + 7;

  

int dp[100001][10];

  

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

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments