Recuento de números del rango [L, R] que contiene al menos un dígito que divide a K

Dados tres enteros positivos L , R y K . La tarea es encontrar el conteo de todos los números del rango [L, R] que contiene al menos un dígito que divide el número K .

Ejemplos: 

Entrada: L = 5, R = 11, K = 10 
Salida: 3 
5, 10 y 11 son solo esos números.

Entrada: L = 32, R = 38, K = 13 
Salida: 0 
 

Enfoque: Inicialice count = 0 y para cada elemento en el rango [L, R] , verifique si contiene al menos un dígito que divide a K. Si es así, entonces incremente el conteo.

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if num
// contains at least one digit
// that divides k
bool digitDividesK(int num, int k)
{
    while (num) {
 
        // Get the last digit
        int d = num % 10;
 
        // If the digit is non-zero
        // and it divides k
        if (d != 0 and k % d == 0)
            return true;
 
        // Remove the last digit
        num = num / 10;
    }
 
    // There is no digit in num
    // that divides k
    return false;
}
 
// Function to return the required
// count of elements from the given
// range which contain at least one
// digit that divides k
int findCount(int l, int r, int k)
{
 
    // To store the result
    int count = 0;
 
    // For every number from the range
    for (int i = l; i <= r; i++) {
 
        // If any digit of the current
        // number divides k
        if (digitDividesK(i, k))
            count++;
    }
    return count;
}
 
// Driver code
int main()
{
    int l = 20, r = 35;
    int k = 45;
 
    cout << findCount(l, r, k);
 
    return 0;
}

// Java implementation of the approach
 
class GFG
{
    // Function that returns true if num
    // contains at least one digit
    // that divides k
    static boolean digitDividesK(int num, int k)
    {
        while (num != 0)
        {
     
            // Get the last digit
            int d = num % 10;
     
            // If the digit is non-zero
            // and it divides k
            if (d != 0 && k % d == 0)
                return true;
     
            // Remove the last digit
            num = num / 10;
        }
     
        // There is no digit in num
        // that divides k
        return false;
    }
     
    // Function to return the required
    // count of elements from the given
    // range which contain at least one
    // digit that divides k
    static int findCount(int l, int r, int k)
    {
     
        // To store the result
        int count = 0;
     
        // For every number from the range
        for (int i = l; i <= r; i++)
        {
     
            // If any digit of the current
            // number divides k
            if (digitDividesK(i, k))
                count++;
        }
        return count;
    }
     
    // Driver code
    public static void main(String []args)
    {
        int l = 20, r = 35;
        int k = 45;
     
        System.out.println(findCount(l, r, k));
    }
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of the approach
 
# Function that returns true if num
# contains at least one digit
# that divides k
def digitDividesK(num, k):
    while (num):
 
        # Get the last digit
        d = num % 10
 
        # If the digit is non-zero
        # and it divides k
        if (d != 0 and k % d == 0):
            return True
 
        # Remove the last digit
        num = num // 10
 
    # There is no digit in num
    # that divides k
    return False
 
# Function to return the required
# count of elements from the given
# range which contain at least one
# digit that divides k
def findCount(l, r, k):
 
    # To store the result
    count = 0
 
    # For every number from the range
    for i in range(l, r + 1):
 
        # If any digit of the current
        # number divides k
        if (digitDividesK(i, k)):
            count += 1
 
    return count
 
# Driver code
l = 20
r = 35
k = 45
 
print(findCount(l, r, k))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
 
class GFG
{
    // Function that returns true if num
    // contains at least one digit
    // that divides k
    static bool digitDividesK(int num, int k)
    {
        while (num != 0)
        {
     
            // Get the last digit
            int d = num % 10;
     
            // If the digit is non-zero
            // and it divides k
            if (d != 0 && k % d == 0)
                return true;
     
            // Remove the last digit
            num = num / 10;
        }
     
        // There is no digit in num
        // that divides k
        return false;
    }
     
    // Function to return the required
    // count of elements from the given
    // range which contain at least one
    // digit that divides k
    static int findCount(int l, int r, int k)
    {
     
        // To store the result
        int count = 0;
     
        // For every number from the range
        for (int i = l; i <= r; i++)
        {
     
            // If any digit of the current
            // number divides k
            if (digitDividesK(i, k))
                count++;
        }
        return count;
    }
     
    // Driver code
    public static void Main()
    {
        int l = 20, r = 35;
        int k = 45;
     
        Console.WriteLine(findCount(l, r, k));
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
// Javascript implementation of the approach
 
// Function that returns true if num
// contains at least one digit
// that divides k
function digitDividesK(num, k)
{
    while (num)
    {
         
        // Get the last digit
        let d = num % 10;
 
        // If the digit is non-zero
        // and it divides k
        if (d != 0 && k % d == 0)
            return true;
 
        // Remove the last digit
        num = parseInt(num / 10);
    }
 
    // There is no digit in num
    // that divides k
    return false;
}
 
// Function to return the required
// count of elements from the given
// range which contain at least one
// digit that divides k
function findCount(l, r, k)
{
 
    // To store the result
    let count = 0;
 
    // For every number from the range
    for(let i = l; i <= r; i++)
    {
         
        // If any digit of the current
        // number divides k
        if (digitDividesK(i, k))
            count++;
    }
    return count;
}
 
// Driver code
let l = 20, r = 35;
let k = 45;
 
document.write(findCount(l, r, k));
 
// This code is contributed by souravmahato348
 
</script>

10

Complejidad de tiempo: O((rl)*(log ₁₀ (num)))
Espacio auxiliar: O(1)