Wednesday, 27 Oct 2021

# Count N-digit numbers such that every position is divisible by the digit at that position

Given a positive integer N, the task is to count the number of N-digit numbers such that every index (1-based indexing) in the number is divisible by the digit occurring at that index. Since the court can be very large, print it modulo 109 + 7.Examples:Input: N = 2Output: 2Explanation: The numbers 11 and 12 are the only 2-digit numbers satisfying the condition.Input: N = 5Output: 24Naive Approach: The simplest approach to solve the problem is to generate all possible N-digit numbers and for each such number, check if all its digits satisfy the required condition or not.Time Complexity: O(10N*N)Auxiliary Space: O(1)Efficient Approach: To optimize the above approach, the idea is to observe the fact that for every position, there are 9 possible options from 1 to 9. Check for every possible option and find the result. Follow the steps below to solve this problem:Initialize the variable ans as 1 to store the answer.Iterate over the range [1, N] using the variable index and perform the following tasks:Initialize the variable, say choices as 0, to store the number of options for that particular index.Iterate over the range [1, 9] using a variable digit and perform the following tasks:If index%digit is equal to 0, then increase the value of choices by 1.Set the value of ans as (ans*1LL*choices)%mod.After performing the above steps, print the value of ans as the answer.Below is the implementation of the above approach:C++#include using namespace std;const int mod = 1e9 + 7;void countOfNumbers(int N){        int ans = 1;        for (int index = 1; index