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 = 2
Output: 2
Explanation: The numbers 11 and 12 are the only 2-digit numbers satisfying the condition.Input: N = 5
Output: 24
Naive 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++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; // Function to count N-digit numbers // such that each position is divisible // by the digit occurring at that position void countOfNumbers( int N) { // Stores the answer. int ans = 1; // Iterate from indices 1 to N for ( int index = 1; index <= N; ++index) { // Stores count of digits that can // be placed at the current index int choices = 0; // Iterate from digit 1 to 9 for ( int digit = 1; digit <= 9; ++digit) { // If index is divisible by digit if (index % digit == 0) { ++choices; } } // Multiply answer with possible choices ans = (ans * 1LL * choices) % mod; } cout << ans << endl; } // Driver Code int main() { // Given Input int N = 5; // Function call countOfNumbers(N); return 0; } |
Java
// Java program for the above approach import java.lang.*; import java.util.*; class GFG{ static int mod = 1000000007 ; // Function to count N-digit numbers // such that each position is divisible // by the digit occurring at that position static void countOfNumbers( int N) { // Stores the answer. int ans = 1 ; // Iterate from indices 1 to N for ( int index = 1 ; index <= N; ++index) { // Stores count of digits that can // be placed at the current index int choices = 0 ; // Iterate from digit 1 to 9 for ( int digit = 1 ; digit <= 9 ; ++digit) { // If index is divisible by digit if (index % digit == 0 ) { ++choices; } } // Multiply answer with possible choices ans = (ans * choices) % mod; } System.out.println(ans); } // Driver Code public static void main(String[] args) { // Given Input int N = 5 ; // Function call countOfNumbers(N); } } // This code is contributed by shivanisinghss2110 |
Python3
# python program for the above approach mod = 1000000000 + 7 # Function to count N-digit numbers # such that each position is divisible # by the digit occurring at that position def countOfNumbers(N): # Stores the answer. ans = 1 # Iterate from indices 1 to N for index in range ( 1 , N + 1 ): # Stores count of digits that can # be placed at the current index choices = 0 # Iterate from digit 1 to 9 for digit in range ( 1 , 10 ): # If index is divisible by digit if (index % digit = = 0 ): choices + = 1 # Multiply answer with possible choices ans = (ans * choices) % mod print (ans) # Driver Code # Given Input N = 5 # Function call countOfNumbers(N) # This code is contributed by amreshkumar3. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ static int mod = 1000000007; // Function to count N-digit numbers // such that each position is divisible // by the digit occurring at that position static void countOfNumbers( int N) { // Stores the answer. int ans = 1; // Iterate from indices 1 to N for ( int index = 1; index <= N; ++index) { // Stores count of digits that can // be placed at the current index int choices = 0; // Iterate from digit 1 to 9 for ( int digit = 1; digit <= 9; ++digit) { // If index is divisible by digit if (index % digit == 0) { ++choices; } } // Multiply answer with possible choices ans = (ans * choices) % mod; } Console.Write(ans); } // Driver Code public static void Main() { // Given Input int N = 5; // Function call countOfNumbers(N); } } // This code is contributed by bgangwar59. |
Javascript
<script> // JavaScript program for the above approach const mod = 1e9 + 7; // Function to count N-digit numbers // such that each position is divisible // by the digit occurring at that position function countOfNumbers(N) { // Stores the answer. let ans = 1; // Iterate from indices 1 to N for (let index = 1; index <= N; ++index) { // Stores count of digits that can // be placed at the current index let choices = 0; // Iterate from digit 1 to 9 for (let digit = 1; digit <= 9; ++digit) { // If index is divisible by digit if (index % digit == 0) { ++choices; } } // Multiply answer with possible choices ans = (ans * 1 * choices) % mod; } document.write(ans); } // Driver Code // Given Input let N = 5; // Function call countOfNumbers(N); // This code is contributed by Potta Lokesh </script> |
24
Time Complexity: O(10 * N)
Auxiliary Space: O(1)