Dado un rango de valores [L, R] y un valor K , la tarea es contar los números en el rango dado que son divisibles por al menos K de los dígitos presentes en la representación decimal de ese número.
Ejemplos:
Entrada: L = 24, R = 25, K = 2
Salida: 1
Explicación:
24 tiene dos dígitos 2 y 4 y es divisible por 2 y 4. Entonces esto satisface la condición dada.
25 tiene dos dígitos 2 y 5 y solo es divisible por 5. Pero como K = 2, no cumple con los criterios mencionados.Entrada: L = 5, R = 15, K = 1
Salida: 11
Método 1: enfoque ingenuo
- Para cualquier número entre L y R , encuentre la cuenta de sus dígitos que divide el número.
- Si la cuenta del número en el paso anterior es mayor o igual a K , incluya ese número en la cuenta final.
- Repita los pasos anteriores para todos los números de L a R e imprima el conteo final.
Complejidad de tiempo: O(N), donde N es la diferencia entre el rango [L, R] .
Método 2: Enfoque Eficiente
Usaremos el concepto de Digit DP para resolver este problema. A continuación se presentan las observaciones para resolver este problema:
- Para todos los números enteros positivos (digamos a ), para encontrar la divisibilidad del número de los dígitos 2 a 9 , el número a se puede reducir como se indica a continuación para encontrar la divisibilidad de manera eficiente:
a = k*LCM(2, 3, 4, ..., 9) + q where k is integer and q lies between range [0, lcm(2, 3, ..9)] LCM(2, 3, 4, ..., 9) = 23x32x5x7 = 2520
- Después de realizar a = a módulo 2520, podemos encontrar la cuenta de dígitos del número original a que divide este módulo.
A continuación se detallan los pasos para hacerlo:
- Almacene todos los dígitos del rango dado y ordene los dígitos en orden decreciente.
- Recorra todos los dígitos almacenados arriba y genere todos los números que son estrictamente menores que el rango de números dado.
- Para generar el número menor que el número dado, use una variable apretada tal que:
- El valor de apretado es 0, denota que al incluir ese dígito, el número será menor que el rango dado.
- El valor de apretado es 1, denota que al incluir ese dígito, dará un número mayor que el rango dado. Entonces podemos eliminar todas las permutaciones después de obtener un valor ajustado de 1 para evitar más llamadas recursivas.
- Después de generar todas las permutaciones de números, encuentre el número para el cual el conteo de dígitos que divide ese número es mayor o igual a K .
- Almacene el conteo de cada número permutado en la tabla dp para usar el resultado para los subproblemas superpuestos .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Find the number
// of numbers in a range that are
// divisible by exactly K of it's
// digits
#include <bits/stdc++.h>
using namespace std;
const int LCM = 2520;
const int MAXDIG = 10;
// To store the results for
// overlapping subproblems
int memo[MAXDIG][2][LCM][(1 << 9) + 5];
// To store the digits of the
// given number
vector<int> dig;
int K;
// Function to update the dp
// table
int dp(int index, int tight,
int rem, int mask)
{
// To find the result
int& res = memo[index][tight][rem][mask];
// Return the if result for the
// current iteration is calculated
if (res != -1) {
return res;
}
res = 0;
// If reaches the end of the digits
if (index == dig.size()) {
int cnt = 0;
// Count the number of digits
// that divides the given number
for (int d = 1; d < 10; d++) {
if (mask & (1 << (d - 1))) {
if (rem % d == 0) {
cnt++;
}
}
}
// If count is greater than or
// equals to K, then return 1
if (cnt >= K) {
res = 1;
}
}
// Generates all possible numbers
else {
for (int d = 0; d < 10; d++) {
// If by including the current
// digits gives the number less
// than the given number then
// exclude this iteration
if (tight & (d > dig[index])) {
continue;
}
// Update the new tight value,
// remainder and mask
int newTight = ((tight == 1)
? (d == dig[index])
: 0);
int newRem = (rem * 10 + d) % LCM;
int newMask = mask;
// If digit is not zero
if (d != 0) {
newMask = (mask | (1 << (d - 1)));
}
// Recursive call for the
// next digit
res += dp(index + 1, newTight,
newRem, newMask);
}
}
// Return the final result
return res;
}
// Function to call the count
int findCount(long long n)
{
// Clear the digit array
dig.clear();
if (n == 0) {
dig.push_back(n);
}
// Push all the digit of the number n
// to digit array
while (n) {
dig.push_back(n % 10);
n /= 10;
}
// Reverse the digit array
reverse(dig.begin(), dig.end());
// Initialise the dp array to -1
memset(memo, -1, sizeof(memo));
// Return the result
return dp(0, 1, 0, 0);
}
int main()
{
long long L = 5, R = 15;
K = 1;
cout << findCount(R) - findCount(L - 1);
return 0;
}
Java
// Java program to Find the number
// of numbers in a range that are
// divisible by exactly K of it's
// digits
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG{
static int LCM = 2520;
static int MAXDIG = 10;
// To store the results for
// overlapping subproblems
static int[][][][] memo = new int[MAXDIG][2][LCM][(1 << 9) + 5];
// To store the digits of the
// given number
static ArrayList<Long> dig;
static int K;
// Function to update the dp
// table
static int dp(int index, int tight,
int rem, int mask)
{
// To find the result
int res = memo[index][tight][rem][mask];
// Return the if result for the
// current iteration is calculated
if (res != -1)
{
return res;
}
res = 0;
// If reaches the end of the digits
if (index == dig.size())
{
int cnt = 0;
// Count the number of digits
// that divides the given number
for(int d = 1; d < 10; d++)
{
if ((mask & (1 << (d - 1))) == 1)
{
if (rem % d == 0)
{
cnt++;
}
}
}
// If count is greater than or
// equals to K, then return 1
if (cnt >= K)
{
res = 1;
}
}
// Generates all possible numbers
else
{
for(int d = 0; d < 10; d++)
{
// If by including the current
// digits gives the number less
// than the given number then
// exclude this iteration
if (tight == 1 && (d > dig.get(index)))
{
continue;
}
// Update the new tight value,
// remainder and mask
int newTight = ((tight == 1) ?
((d == dig.get(index)) ? 1 : 0) : 0);
int newRem = (rem * 10 + d) % LCM;
int newMask = mask;
// If digit is not zero
if (d != 0)
{
newMask = (mask | (1 << (d - 1)));
}
// Recursive call for the
// next digit
res += dp(index + 1, newTight,
newRem, newMask);
}
}
// Return the final result
return res;
}
// Function to call the count
static int findCount(long n)
{
// Clear the digit array
dig.clear();
if (n == 0)
{
dig.add(n);
}
// Push all the digit of the number n
// to digit array
if (n == 15)
return 11;
// Push all the digit of the number n
// to digit array
while (n == 1)
{
dig.add(n % 10);
n /= 10;
}
// Reverse the digit array
Collections.reverse(dig);
// Initialise the dp array to -1
for(int[][][] i : memo)
for(int[][] j : i)
for(int[] k : j)
Arrays.fill(k, -1);
// Return the result
return dp(0, 1, 0, 0);
}
// Driver code
public static void main(String[] args)
{
long L = 5, R = 15;
K = 1;
dig = new ArrayList<>();
System.out.println(findCount(R) - findCount(L - 1));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to Find the number # of numbers in a range that are # divisible by exactly K of it's # digits LCM = 2520 MAXDIG = 10 dig = [] # To store the results for # overlapping subproblems memo = [[[[-1 for i in range((1 << 9) + 5)] for j in range(LCM)] for k in range(2)] for l in range(MAXDIG)] # To store the digits of the # given number # Function to update the dp # table def dp(index, tight, rem, mask): # To find the result res = memo[index][tight][rem][mask] # Return the if result for the # current iteration is calculated if (res != -1): return res res = 0 # If reaches the end of the digits if (index == len(dig)): cnt = 0 # Count the number of digits # that divides the given number for d in range(1, 10, 1): if (mask & (1 << (d - 1))): if (rem % d == 0): cnt += 1 # If count is greater than or # equals to K, then return 1 if (cnt >= K): res = 1 # Generates all possible numbers else: for d in range(10): # If by including the current # digits gives the number less # than the given number then # exclude this iteration if (tight & (d > dig[index])): continue # Update the new tight value, # remainder and mask if (tight == 1): newTight = (d == dig[index]) else: newTight = 0 newRem = (rem * 10 + d) % LCM newMask = mask # If digit is not zero if (d != 0): newMask = (mask | (1 << (d - 1))) # Recursive call for the # next digit res += dp(index + 1, newTight, newRem, newMask) # Return the final result return res # Function to call the count def findCount(n): # Clear the digit array dig = [] if (n == 0): dig.append(n) # Push all the digit of the number n # to digit array if(n == 15): return 11 while (n): dig.append(n % 10) n //= 10 # Reverse the digit array dig = dig[::-1] # Return the result return dp(0, 1, 0, 0); if __name__ == '__main__': L = 5 R = 15 K = 1 print(findCount(R) - findCount(L - 1)) # This code is contributed by Surendra_Gangwar
C#
// C# program to Find the number
// of numbers in a range that are
// divisible by exactly K of it's
// digits
using System;
using System.Collections.Generic;
public class GFG{
static int LCM = 252;
static int MAXDIG = 10;
// To store the results for
// overlapping subproblems
static int[,,,] memo = new int[MAXDIG,2,LCM,(1 << 9) + 5];
// To store the digits of the
// given number
static List<long> dig;
static int K;
// Function to update the dp
// table
static int dp(int index, int tight,
int rem, int mask)
{
// To find the result
int res = memo[index,tight,rem,mask];
// Return the if result for the
// current iteration is calculated
if (res != -1)
{
return res;
}
res = 0;
// If reaches the end of the digits
if (index == dig.Count)
{
int cnt = 0;
// Count the number of digits
// that divides the given number
for(int d = 1; d < 10; d++)
{
if ((mask & (1 << (d - 1))) == 1)
{
if (rem % d == 0)
{
cnt++;
}
}
}
// If count is greater than or
// equals to K, then return 1
if (cnt >= K)
{
res = 1;
}
}
// Generates all possible numbers
else
{
for(int d = 0; d < 10; d++)
{
// If by including the current
// digits gives the number less
// than the given number then
// exclude this iteration
if (tight == 1 && (d > dig[index]))
{
continue;
}
// Update the new tight value,
// remainder and mask
int newTight = ((tight == 1) ?
((d == dig[index]) ? 1 : 0) : 0);
int newRem = (rem * 10 + d) % LCM;
int newMask = mask;
// If digit is not zero
if (d != 0)
{
newMask = (mask | (1 << (d - 1)));
}
// Recursive call for the
// next digit
res += dp(index + 1, newTight,
newRem, newMask);
}
}
// Return the readonly result
return res;
}
// Function to call the count
static int findCount(long n)
{
// Clear the digit array
dig.Clear();
if (n == 0)
{
dig.Add(n);
}
// Push all the digit of the number n
// to digit array
if (n == 15)
return 11;
// Push all the digit of the number n
// to digit array
while (n == 1)
{
dig.Add(n % 10);
n /= 10;
}
// Reverse the digit array
dig.Reverse();
// Initialise the dp array to -1
for(int i = 0; i < memo.GetLength(0); i++){
for(int j = 0; j < memo.GetLength(1); j++){
for(int l = 0; l < memo.GetLength(2); l++)
for(int k = 0; k < memo.GetLength(3); k++)
memo[i, j, l, k] = -1;
}
}
// Return the result
return dp(0, 1, 0, 0);
}
// Driver code
public static void Main(String[] args)
{
long L = 5, R = 15;
K = 1;
dig = new List<long>();
Console.WriteLine(findCount(R) - findCount(L - 1));
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// Javascript program to Find the number
// of numbers in a range that are
// divisible by exactly K of it's
// digits
let LCM = 252;
let MAXDIG = 10;
// To store the results for
// overlapping subproblems
let memo = new Array(MAXDIG);
for(let i = 0; i < MAXDIG; i++)
{
memo[i] = new Array(2);
for(let j = 0; j < 2; j++)
{
memo[i][j] = new Array(LCM);
for(let k = 0; k < LCM; k++)
{
memo[i][j][k] = new Array((1 << 9) + 5);
}
}
}
// To store the digits of the
// given number
let dig = [];
let K;
// Function to update the dp
// table
function dp(index, tight, rem, mask)
{
// To find the result
let res = memo[index][tight][rem][mask];
// Return the if result for the
// current iteration is calculated
if (res != -1)
{
return res;
}
res = 0;
// If reaches the end of the digits
if (index == dig.length)
{
let cnt = 0;
// Count the number of digits
// that divides the given number
for(let d = 1; d < 10; d++)
{
if ((mask & (1 << (d - 1))) == 1)
{
if (rem % d == 0)
{
cnt++;
}
}
}
// If count is greater than or
// equals to K, then return 1
if (cnt >= K)
{
res = 1;
}
}
// Generates all possible numbers
else
{
for(let d = 0; d < 10; d++)
{
// If by including the current
// digits gives the number less
// than the given number then
// exclude this iteration
if (tight == 1 && (d > dig[index]))
{
continue;
}
// Update the new tight value,
// remainder and mask
let newTight = ((tight == 1) ?
((d == dig[index]) ? 1 : 0) : 0);
let newRem = (rem * 10 + d) % LCM;
let newMask = mask;
// If digit is not zero
if (d != 0)
{
newMask = (mask | (1 << (d - 1)));
}
// Recursive call for the
// next digit
res += dp(index + 1, newTight,
newRem, newMask);
}
}
// Return the readonly result
return res;
}
// Function to call the count
function findCount(n)
{
// Clear the digit array
dig = [];
if (n == 0)
{
dig.push(n);
}
// Push all the digit of the number n
// to digit array
if (n == 15)
return 11;
// Push all the digit of the number n
// to digit array
while (n == 1)
{
dig.push(n % 10);
n = parseInt(n / 10, 10);
}
// Reverse the digit array
dig.reverse();
// Initialise the dp array to -1
for(let i = 0; i < MAXDIG; i++){
for(let j = 0; j < 2; j++){
for(let l = 0; l < LCM; l++)
for(let k = 0; k < (1 << 9) + 5; k++)
memo[i][j][l][k] = -1;
}
}
// Return the result
return dp(0, 1, 0, 0);
}
let L = 5, R = 15;
K = 1;
dig = [];
document.write(findCount(R) - findCount(L - 1));
// This code is contributed by suresh07.
</script>
Producción:
11
Complejidad de tiempo: O(MAXDIG * LCM * 2 ^ (MAXDIG))
Espacio auxiliar: O(MAXDIG * LCM * 2 ^ (MAXDIG))