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 positionvoid 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 Codeint main(){ // Given Input int N = 5; // Function call countOfNumbers(N); return 0;} |
Java
// Java program for the above approachimport 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 positionstatic 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 Codepublic 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 approachmod = 1000000000 + 7# Function to count N-digit numbers# such that each position is divisible# by the digit occurring at that positiondef 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 InputN = 5# Function callcountOfNumbers(N)# This code is contributed by amreshkumar3. |
C#
// C# program for the above approachusing 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 positionstatic 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 Codepublic 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> |
Output:
24
Time Complexity: O(10 * N)
Auxiliary Space: O(1)
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!