Cuente los divisores de n que tienen al menos un dígito común con n

Dado un número n, encuentre el número de divisores cuyo al menos un dígito en la representación decimal coincida con el número n.
 

Ejemplos:  

Input : n = 10
Output: 2
Explanation: numbers are 1 and 10, 1 and 10 
both have a nimbus of 1 digit common with n = 10.

Input : n = 15 
Output: 3 
Explanation: the numbers are 1, 5, 15, all of them
have a minimum of 1 digit common. 

Un enfoque ingenuo es iterar de 1 a n y verificar todos los divisores y usar hash para determinar si alguno de los dígitos coincide con n o no. 
Complejidad de tiempo: O(n) 
Espacio auxiliar: O(1) 
Un enfoque eficiente es iterar de 1 a sqrt(n) y verificar todos los divisores i y n/i, si ambos son diferentes, verificamos si hay alguno coincide con i y n/i, si es así, simplemente agregamos 1 a la respuesta. Usamos hashing para almacenar si un número está presente o no. 
A continuación se muestra la implementación del enfoque anterior.  

C++

// C++ program to count divisors of n that have at least
// one digit common with n
#include <bits/stdc++.h>
using namespace std;
 
// function to return true if any digit of m is
// present in hash[].
bool isDigitPresent(int m, bool hash[])
{
    // check till last digit
    while (m) {
 
        // if number is also present in original number
        // then return true
        if (hash[m % 10])
            return true;
        m = m / 10;
    }
 
    // if no number matches then return 1
    return false;
}
 
// Count the no of divisors that have at least 1 digits
// same
int countDivisibles(int n)
{
    // Store digits present in n in a hash[]
    bool hash[10] = { 0 };
    int m = n;
    while (m) {
 
        // marks that the number is present
        hash[m % 10] = true;
 
        // last digit removed
        m = m / 10;
    }
 
    // loop to traverse from 1 to sqrt(n) to
    // count divisors
    int ans = 0;
    for (int i = 1; i <= sqrt(n); i++) {
 
        // if i is the factor
        if (n % i == 0) {
 
            // call the function to check if any
            // digits match or not
            if (isDigitPresent(i, hash))
                ans++;
 
            if (n / i != i) {
 
                // if n/i != i then a different number,
                // then check it also
                if (isDigitPresent(n/i, hash))
                ans++;
            }
        }
    }
 
    // return the answer
    return ans;
}
 
// driver program to test the above function
int main()
{
    int n = 15;
    cout << countDivisibles(n);
    return 0;
}

Java

// Java program to count divisors of n that
// have at least one digit common with n
class GFG {
     
    // function to return true if any digit
    // of m is present in hash[].
    static boolean isDigitPresent(int m,
                            boolean hash[])
    {
         
        // check till last digit
        while (m > 0) {
     
            // if number is also present
            // in original number then
            // return true
            if (hash[m % 10])
                return true;
            m = m / 10;
        }
     
        // if no number matches then
        // return 1
        return false;
    }
     
    // Count the no of divisors that
    // have at least 1 digits same
    static int countDivisibles(int n)
    {
         
        // Store digits present in n
        // in a hash[]
        boolean hash[] = new boolean[10];
        int m = n;
        while (m > 0) {
     
            // marks that the number
            // is present
            hash[m % 10] = true;
     
            // last digit removed
            m = m / 10;
        }
     
        // loop to traverse from 1 to
        // sqrt(n) to count divisors
        int ans = 0;
        for (int i = 1; i <= Math.sqrt(n);
                                    i++)
        {
     
            // if i is the factor
            if (n % i == 0) {
     
                // call the function to
                // check if any digits
                // match or not
                if (isDigitPresent(i, hash))
                    ans++;
     
                if (n / i != i) {
     
                    // if n/i != i then a
                    // different number,
                    // then check it also
                    if (isDigitPresent(n/i, hash))
                        ans++;
                }
            }
        }
     
        // return the answer
        return ans;
    }
     
    //driver code
    public static void main (String[] args)
    {
        int n = 15;
         
        System.out.print(countDivisibles(n));
    }
}
 
// This code is contributed by Anant Agarwal.

Python3

# Python3 program to count divisors
# of n that have at least
# one digit common with n
import math
 
# Function to return true if any 
# digit of m is present in hash[].
def isDigitPresent(m, Hash):
 
    # check till last digit
    while (m):
 
        # if number is also present in original 
        # number then return true
        if (Hash[m % 10]):
            return True
        m = m // 10
 
    # if no number matches then return 1
    return False
 
# Count the no of divisors that
# have at least 1 digits same
def countDivisibles(n):
 
    # Store digits present in n in a hash[]
    Hash = [False for i in range(10)]
    m = n
    while (m):
 
        # marks that the number is present
        Hash[m % 10] = True
 
        # last digit removed
        m = m // 10
     
 
    # loop to traverse from 1 to sqrt(n) to
    # count divisors
    ans = 0
    for i in range(1, int(math.sqrt(n)) + 1):
 
        # if i is the factor
        if (n % i == 0):
 
            # call the function to check if any
            # digits match or not
            if (isDigitPresent(i, Hash)):
                ans += 1
 
            if (n // i != i):
 
                # if n/i != i then a different number,
                # then check it also
                if (isDigitPresent(n // i, Hash)):
                    ans += 1
 
    # return the answer
    return ans
 
# Driver Code
n = 15
print(countDivisibles(n))
 
# This code is contributed by Anant Agarwal.

C#

// Program to count divisors of
// n that have at least one digit
// common with n
using System;
 
class GFG {
 
    // function to return true if
    // any digit of m is present
    // in hash[].
    static bool isDigitPresent(int m, bool[] hash)
    {
        // check till last digit
        while (m > 0) {
 
            // if number is also present in the
            // original number then return true
            if (hash[m % 10])
                return true;
            m = m / 10;
        }
 
        // if no number matches then return 1
        return false;
    }
 
    // Count the no of divisors that have
    // at least 1 digits same
    static int countDivisibles(int n)
    {
        // Store digits present in n in a hash[]
        bool[] hash = new bool[10];
        int m = n;
        while (m > 0) {
 
            // marks that the number is present
            hash[m % 10] = true;
 
            // last digit removed
            m = m / 10;
        }
 
        // loop to traverse from 1 to sqrt(n) to
        // count divisors
        int ans = 0;
        for (int i = 1; i <= Math.Sqrt(n); i++) {
 
            // if i is the factor
            if (n % i == 0) {
 
                // call the function to check if any
                // digits match or not
                if (isDigitPresent(i, hash))
                    ans++;
 
                if (n / i != i) {
 
                    // if n/i != i then a different number,
                    // then check it also
                    if (isDigitPresent(n / i, hash))
                        ans++;
                }
            }
        }
 
        // return the answer
        return ans;
    }
 
    // Driver code
    public static void Main()
    {
        int n = 15;
        Console.Write(countDivisibles(n));
    }
}
 
// This code is contributed by Anant Agarwal.

PHP

<?php
// PHP program to count divisors
// of n that have at least
// one digit common with n
 
// function to return true
// if any digit of m is
// present in hash[].
function isDigitPresent($m, $hash)
{
    // check till last digit
    while ($m)
    {
 
        // if number is also
        // present in original
        // number then return true
        if ($hash[$m % 10])
            return true;
        $m = (int)($m / 10);
    }
 
    // if no number matches
    // then return 1
    return false;
}
 
// Count the no of divisors
// that have at least 1 digits
// same
function countDivisibles($n)
{
    // Store digits present
    // in n in a hash[]
    $hash = array_fill(0, 10, false);
    $m = $n;
    while ($m)
    {
 
        // marks that the
        // number is present
        $hash[$m % 10] = true;
 
        // last digit removed
        $m = (int)($m / 10);
    }
 
    // loop to traverse from
    // 1 to sqrt(n) to count divisors
    $ans = 0;
    for ($i = 1; $i <= sqrt($n); $i++)
    {
 
        // if i is the factor
        if ($n % $i == 0)
        {
 
            // call the function
            // to check if any
            // digits match or not
            if (isDigitPresent($i, $hash))
                $ans++;
 
            if ((int)($n / $i) != $i)
            {
 
                // if n/i != i then a
                // different number,
                // then check it also
                if (isDigitPresent((int)($n / $i), $hash))
                $ans++;
            }
        }
    }
 
    // return the answer
    return $ans;
}
 
// Driver code
$n = 15;
echo countDivisibles($n);
     
// This code is contributed by mits
?>

Javascript

<script>
// JavaScript program to count divisors of n that
// have at least one digit common with n
 
    // function to return true if any digit
    // of m is present in hash[].
    function isDigitPresent(m, hash)
    {
         
        // check till last digit
        while (m > 0) {
     
            // if number is also present
            // in original number then
            // return true
            if (hash[m % 10])
                return true;
            m = Math.floor(m / 10);
        }
     
        // if no number matches then
        // return 1
        return false;
    }
     
    // Count the no of divisors that
    // have at least 1 digits same
    function countDivisibles(n)
    {
         
        // Store digits present in n
        // in a hash[]
        let hash = Array.from({length: 10}, (_, i) => 0);
        let m = n;
        while (m > 0) {
     
            // marks that the number
            // is present
            hash[m % 10] = true;
     
            // last digit removed
            m = Math.floor(m / 10);
        }
     
        // loop to traverse from 1 to
        // sqrt(n) to count divisors
        let ans = 0;
        for (let i = 1; i <= Math.sqrt(n);
                                    i++)
        {
     
            // if i is the factor
            if (n % i == 0) {
     
                // call the function to
                // check if any digits
                // match or not
                if (isDigitPresent(i, hash))
                    ans++;
     
                if (n / i != i) {
     
                    // if n/i != i then a
                    // different number,
                    // then check it also
                    if (isDigitPresent(n/i, hash))
                        ans++;
                }
            }
        }
     
        // return the answer
        return ans;
    }
     
  
// Driver Code
 
    let n = 15;
         
    document.write(countDivisibles(n));
         
</script>

Producción: 

3

Complejidad de tiempo: O(sqrt n) 
Espacio auxiliar: O(1) 
Este artículo es una contribución de Raja Vikramaditya . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *