Dado un entero positivo N , la tarea es contar la cantidad de números de N dígitos de manera que cada índice (indexación basada en 1) en el número sea divisible por el dígito que se encuentra en ese índice. Como la cancha puede ser muy grande, imprímela módulo 10 9 + 7 .
Ejemplos:
Entrada: N = 2
Salida: 2
Explicación: Los números 11 y 12 son los únicos números de 2 dígitos que cumplen la condición.Entrada: N = 5
Salida: 24
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los números de N dígitos posibles y, para cada uno de esos números, verificar si todos sus dígitos satisfacen la condición requerida o no.
Complejidad temporal: O(10 N *N)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es observar el hecho de que para cada posición, hay 9 opciones posibles del 1 al 9. Verifique cada opción posible y encuentre el resultado.
Siga los pasos a continuación para resolver este problema:
- Inicialice la variable ans como 1 para almacenar la respuesta.
- Iterar sobre el rango [1, N] usando el índice variable y realizar las siguientes tareas:
- Inicialice la variable, digamos opciones como 0, para almacenar la cantidad de opciones para ese índice en particular.
- Iterar sobre el rango [1, 9] usando un dígito variable y realizar las siguientes tareas:
- Si index%digit es igual a 0, aumente el valor de las opciones en 1.
- Establezca el valor de ans como (ans*1LL*choices)%mod .
- Después de realizar los pasos anteriores, imprima el valor de ans como respuesta.
A continuación se muestra la implementación del enfoque anterior:
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
Complejidad de Tiempo: O(10 * N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA