Given a number N, the task is to count the number of ways to create an N digit number from digits 1 to 9 such that every digit is divisible by its previous digit that is if the number is represented by an array of digits A then A[i + 1] % A[i] == 0. print the answer modulo 109 + 7.
Examples:
Input: N = 2
Output: 23
Explanation: For N = 2 possible answers 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.Input: N = 3
Output: 44
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(9N)
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
- dp[i][j] represents the number of ways of creating a number of size i and j is its previous digit taken.
- 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 by storing 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 two parameters representing ith position to be filled and j representing the last digit taken.
- Call the recursive function for choosing all digits from 1 to 9.
- Base case if all positions filled return 1.
- Create a 2d array of dp[N][10] initially filled with -1.
- If the answer for a particular state is computed then save it in dp[i][j].
- If the answer for a particular state is already computed then just return dp[i][j].
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;const int MOD = 1e9 + 7;// DP table initialized with -1int dp[100001][10];// Recursive Function to find number of N// digits such that its every digit// divisible by its previous digitint recur(int i, int j, int N){ // Base case if (i == N) { return 1; } // If answer for current state is // already calculated then just // return dp[i][j] if (dp[i][j] != -1) return dp[i][j]; // Answer initialized with zero int ans = 0; // First element to decide if (i == 0) { // Iterating for all digits from // 1 to 9 for (int digit = 1; digit <= 9; digit++) { // Choosing this as // current digit ans = (ans + recur(i + 1, digit, N)) % MOD; } } // Choosing for other positions apart // from first else { // Iterating for all digits // from 1 to 9 for (int digit = 1; digit <= 9; digit++) { // Choosing this as current // digit if it is divisible by // previous digit if (digit % j == 0) ans = (ans + recur(i + 1, digit, N)) % MOD; } } // Save and return dp value return dp[i][j] = ans;}// Function to find number of N digits// such that its every digit divisible// by its previous digitint countWays(int N){ // Initializing dp array with - 1 memset(dp, -1, sizeof(dp)); // Calling recursive function for // finding answer int ans = recur(0, 0, N); // Returning the answer return ans;}// Driver Codeint main(){ // Input 1 int N = 2; // Function Call cout << countWays(N) << endl; // Input 2 int N1 = 3; // Function Call cout << countWays(N1) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { static final int MOD = (int)1e9 + 7; static int[][] dp; // Recursive Function to find number of N // digits such that its every digit // divisible by its previous digit static int recur(int i, int j, int N) { // Base case if (i == N) { return 1; } // If answer for current state is // already calculated then just // return dp[i][j] if (dp[i][j] != -1) { return dp[i][j]; } // Answer initialized with zero int ans = 0; // First element to decide if (i == 0) { // Iterating for all digits from // 1 to 9 for (int digit = 1; digit <= 9; digit++) { // Choosing this as // current digit ans = (ans + recur(i + 1, digit, N)) % MOD; } } else { // Choosing for other positions apart // from first // Iterating for all digits // from 1 to 9 for (int digit = 1; digit <= 9; digit++) { // Choosing this as current // digit if it is divisible by // previous digit if (digit % j == 0) { ans = (ans + recur(i + 1, digit, N)) % MOD; } } } // Save and return dp value return dp[i][j] = ans; } // Function to find number of N digits // such that its every digit divisible // by its previous digit static int countWays(int N) { // Initializing dp array with - 1 dp = new int[N + 1][10]; for (int[] row : dp) { Arrays.fill(row, -1); } // Calling recursive function for // finding answer int ans = recur(0, 0, N); // Returning the answer return ans; } public static void main(String[] args) { // Input 1 int N = 2; // Function Call System.out.println(countWays(N)); // Input 2 int N1 = 3; // Function Call System.out.println(countWays(N1)); }}// This code is contributed by lokesh. |
Python3
MOD = 1e9 + 7# DP table initialized with -1dp = [[-1 for j in range(10)] for i in range(100001)]# Recursive Function to find number of N# digits such that its every digit# divisible by its previous digitdef recur(i, j, N): # Base case if i == N: return 1 # If answer for current state is # already calculated then just # return dp[i][j] if dp[i][j] != -1: return dp[i][j] # Answer initialized with zero ans = 0 # First element to decide if i == 0: # Iterating for all digits from # 1 to 9 for digit in range(1, 10): # Choosing this as # current digit ans = (ans + recur(i + 1, digit, N)) % MOD # Choosing for other positions apart # from first else: # Iterating for all digits # from 1 to 9 for digit in range(1, 10): # Choosing this as current # digit if it is divisible by # previous digit if digit % j == 0: ans = (ans + recur(i + 1, digit, N)) % MOD # Save and return dp value dp[i][j] = ans return ans# Function to find number of N digits# such that its every digit divisible# by its previous digitdef count_ways(N): # Calling recursive function for # finding answer ans = recur(0, 0, N) # Returning the answer return ans# Driver Code# Input 1N = 2# Function Callprint(count_ways(N))# Input 2N1 = 3dp = [[-1 for j in range(10)] for i in range(100001)]# Function Callprint(count_ways(N1))# This code is contributed by lokeshpotta20. |
C#
// C# code to implement the approachusing System;public class GFG { static readonly int MOD = (int)1e9 + 7; static int[, ] dp; // Recursive Function to find number of N // digits such that its every digit // divisible by its previous digit static int recur(int i, int j, int N) { // Base case if (i == N) { return 1; } // If answer for current state is // already calculated then just // return dp[i][j] if (dp[i, j] != -1) { return dp[i, j]; } // Answer initialized with zero int ans = 0; // First element to decide if (i == 0) { // Iterating for all digits from // 1 to 9 for (int digit = 1; digit <= 9; digit++) { // Choosing this as // current digit ans = (ans + recur(i + 1, digit, N)) % MOD; } } else { // Choosing for other positions apart // from first // Iterating for all digits // from 1 to 9 for (int digit = 1; digit <= 9; digit++) { // Choosing this as current // digit if it is divisible by // previous digit if (digit % j == 0) { ans = (ans + recur(i + 1, digit, N)) % MOD; } } } // Save and return dp value return dp[i, j] = ans; } // Function to find number of N digits // such that its every digit divisible // by its previous digit static int countWays(int N) { // Initializing dp array with - 1 dp = new int[N + 1, 10]; for (int i = 0; i <= N; i++) { for (int j = 0; j <= 9; j++) { dp[i, j] = -1; } } // Calling recursive function for // finding answer int ans = recur(0, 0, N); // Returning the answer return ans; } static public void Main() { // Input 1 int N = 2; // Function Call Console.WriteLine(countWays(N)); // Input 2 int N1 = 3; // Function Call Console.WriteLine(countWays(N1)); }}// This code is contributed by lokeshmvs21. |
Javascript
// Javascript code to implement the approachconst MOD = 1e9 + 7;// DP table initialized with -1let dp=new Array(1000001);for(let i = 0; i < 1000001; i++) dp[i] = new Array(10).fill(-1);// Recursive Function to find number of N// digits such that its every digit// divisible by its previous digitfunction recur( i, j, N){ // Base case if (i == N) { return 1; } // If answer for current state is // already calculated then just // return dp[i][j] if (dp[i][j] != -1) return dp[i][j]; // Answer initialized with zero let ans = 0; // First element to decide if (i == 0) { // Iterating for all digits from // 1 to 9 for (let digit = 1; digit <= 9; digit++) { // Choosing this as // current digit ans = (ans + recur(i + 1, digit, N)) % MOD; } } // Choosing for other positions apart // from first else { // Iterating for all digits // from 1 to 9 for (let digit = 1; digit <= 9; digit++) { // Choosing this as current // digit if it is divisible by // previous digit if (digit % j == 0) ans = (ans + recur(i + 1, digit, N)) % MOD; } } // Save and return dp value return dp[i][j] = ans;}// Function to find number of N digits// such that its every digit divisible// by its previous digitfunction countWays( N){ // Initializing dp array with - 1 for(let i = 0; i < 100001; i++) { for(let j = 0; j < 10; j++) dp[i][j]=-1; } // Calling recursive function for // finding answer let ans = recur(0, 0, N); // Returning the answer return ans;}// Driver Code// Input 1let N = 2;// Function Callconsole.log(countWays(N));// Input 2let N1 = 3;// Function Callconsole.log(countWays(N1));// This code is contributed by poojaagarwal2. |
Output
23 44
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memorization(top-down) because memorization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a table to store the solution of the subproblems.
- Initialize the table with base cases
- Fill up the table iteratively
- Return the final solution
Implementation :
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const int MOD = 1e9 + 7;// Function to find number of N digits// such that its every digit divisible// by its previous digitint countWays(int N){ // DP table to store the number of // ways for each subproblem vector<vector<int>> dp(N+1, vector<int>(10, 0)); // Base case for (int j = 1; j <= 9; j++) { dp[1][j] = 1; } // Fill the DP table for (int i = 2; i <= N; i++) { for (int j = 1; j <= 9; j++) { for (int k = j; k <= 9; k++) { if (k % j == 0) { dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD; } } } } // Compute the final answer int ans = 0; for (int j = 1; j <= 9; j++) { ans = (ans + dp[N][j]) % MOD; } // Return the answer return ans;}// Driver Codeint main(){ // Input 1 int N = 2; // Function Call cout << countWays(N) << endl; // Input 2 int N1 = 3; // Function Call cout << countWays(N1) << endl; return 0;}// this code is contributed by bhardwajji |
Java
/*package whatever //do not write package name here */// Java program for the above approachimport java.util.*;class GFG { static final int MOD = (int) 1e9 + 7; // Function to find number of N digits // such that its every digit divisible // by its previous digit static int countWays(int N) { // DP table to store the number of // ways for each subproblem int[][] dp = new int[N + 1][10]; // Base case for (int j = 1; j <= 9; j++) { dp[1][j] = 1; } // Fill the DP table for (int i = 2; i <= N; i++) { for (int j = 1; j <= 9; j++) { for (int k = j; k <= 9; k++) { if (k % j == 0) { dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD; } } } } // Compute the final answer int ans = 0; for (int j = 1; j <= 9; j++) { ans = (ans + dp[N][j]) % MOD; } // Return the answer return ans; } // Driver Code public static void main (String[] args) { // Input 1 int N = 2; // Function Call System.out.println(countWays(N)); // Input 2 int N1 = 3; // Function Call System.out.println(countWays(N1)); }}// akashish__ |
Python3
MOD = int(1e9 + 7)# Function to find number of N digits# such that its every digit divisible# by its previous digitdef countWays(N: int) -> int: # DP table to store the number of # ways for each subproblem dp = [[0] * 10 for _ in range(N+1)] # Base case for j in range(1, 10): dp[1][j] = 1 # Fill the DP table for i in range(2, N+1): for j in range(1, 10): for k in range(j, 10): if k % j == 0: dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD # Compute the final answer ans = 0 for j in range(1, 10): ans = (ans + dp[N][j]) % MOD # Return the answer return ans# Driver Codeif __name__ == '__main__': # Input 1 N = 2 # Function Call print(countWays(N)) # Input 2 N1 = 3 # Function Call print(countWays(N1)) |
Javascript
const MOD = 1e9 + 7;// Function to find number of N digits// such that its every digit divisible// by its previous digitfunction countWays(N) { // DP table to store the number of // ways for each subproblem let dp = new Array(N + 1); for (let i = 0; i <= N; i++) { dp[i] = new Array(10).fill(0); } // Base case for (let j = 1; j <= 9; j++) { dp[1][j] = 1; } // Fill the DP table for (let i = 2; i <= N; i++) { for (let j = 1; j <= 9; j++) { for (let k = j; k <= 9; k++) { if (k % j === 0) { dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD; } } } } // Compute the final answer let ans = 0; for (let j = 1; j <= 9; j++) { ans = (ans + dp[N][j]) % MOD; } // Return the answer return ans;}// Driver Codelet N = 2;// Function Callconsole.log(countWays(N));let N1 = 3;// Function Callconsole.log(countWays(N1)); |
C#
using System;using System.Collections.Generic;class GFG { const int MOD = 1000000007; // Function to find number of N digits // such that its every digit divisible // by its previous digit static int countWays(int N) { // DP table to store the number of // ways for each subproblem List<List<int> > dp = new List<List<int> >(); for (int i = 0; i <= N; i++) { dp.Add(new List<int>()); for (int j = 0; j < 10; j++) { dp[i].Add(0); } } // Base case for (int j = 1; j <= 9; j++) { dp[1][j] = 1; } // Fill the DP table for (int i = 2; i <= N; i++) { for (int j = 1; j <= 9; j++) { for (int k = j; k <= 9; k++) { if (k % j == 0) { dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD; } } } } // Compute the final answer int ans = 0; for (int j = 1; j <= 9; j++) { ans = (ans + dp[N][j]) % MOD; } // Return the answer return ans; } // Driver Code static void Main() { // Input 1 int N = 2; // Function Call Console.WriteLine(countWays(N)); // Input 2 int N1 = 3; // Function Call Console.WriteLine(countWays(N1)); }} |
Output
23 44
Time Complexity : O(N)
Auxiliary Space: O(N)
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
