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