Dado un número N que puede tener 10 ^ 5 dígitos, la tarea es contar todos los dígitos en N que dividen N. La divisibilidad por 0 no está permitida. Si cualquier dígito en N que se repite divide a N, entonces todas las repeticiones de ese dígito deben contarse, es decir, N = 122324, aquí 2 divide a N y aparece 3 veces. Así que contar para el dígito 2 será 3.
Ejemplos:
Input : N = "35" Output : 1 There are two digits in N and 1 of them (5)divides it. Input : N = "122324" Output : 5 N is divisible by 1, 2 and 4
¿Cómo verificar la divisibilidad de un dígito para N grande almacenado como string?
La idea es usar la propiedad distributiva de la operación mod.
(x+y)%a = ((x%a) + (y%a)) % a.
// This function returns true if digit divides N,
// else false
bool divisible(string N, int digit)
{
int ans = 0;
for (int i = 0; i < N.length(); i++)
{
// (N[i]-'0') gives the digit value and
// form the number
ans = (ans*10 + (N[i]-'0'));
// We use distributive property of mod here.
ans %= digit;
}
return (ans == 0);
}
Una solución simple para este problema es leer el número en forma de string y verificar uno por uno la divisibilidad por cada dígito que aparece en N. La complejidad del tiempo para este enfoque será O(N 2 ).
Una solución eficiente para este problema es usar una array adicional divide[] de tamaño 10. Dado que solo tenemos 10 dígitos, ejecute un ciclo del 1 al 9 y verifique la divisibilidad de N con cada dígito del 1 al 9. Si cualquier dígito divide N luego marque verdadero en la array divide[] en el dígito como índice. Ahora recorra la string de números e incremente el resultado si divide[i] es verdadero para el dígito actual i.
C++
// C++ program to find number of digits in N that
// divide N.
#include<bits/stdc++.h>
using namespace std;
// Utility function to check divisibility by digit
bool divisible(string N, int digit)
{
int ans = 0;
for (int i = 0; i < N.length(); i++)
{
// (N[i]-'0') gives the digit value and
// form the number
ans = (ans*10 + (N[i]-'0'));
ans %= digit;
}
return (ans == 0);
}
// Function to count digits which appears in N and
// divide N
// divide[10] --> array which tells that particular
// digit divides N or not
// count[10] --> counts frequency of digits which
// divide N
int allDigits(string N)
{
// We initialize all digits of N as not divisible
// by N.
bool divide[10] = {false};
divide[1] = true; // 1 divides all numbers
// start checking divisibility of N by digits 2 to 9
for (int digit=2; digit<=9; digit++)
{
// if digit divides N then mark it as true
if (divisible(N, digit))
divide[digit] = true;
}
// Now traverse the number string to find and increment
// result whenever a digit divides N.
int result = 0;
for (int i=0; i<N.length(); i++)
{
if (divide[N[i]-'0'] == true)
result++;
}
return result;
}
// Driver program to run the case
int main()
{
string N = "122324";
cout << allDigits(N);
return 0;
}
Java
// Java program to find number of digits in N that
// divide N.
import java.util.*;
class solution
{
// Utility function to check divisibility by digit
static boolean divisible(String N, int digit)
{
int ans = 0;
for (int i = 0; i < N.length(); i++)
{
// (N[i]-'0') gives the digit value and
// form the number
ans = (ans*10 + (N.charAt(i)-'0'));
ans %= digit;
}
return (ans == 0);
}
// Function to count digits which appears in N and
// divide N
// divide[10] --> array which tells that particular
// digit divides N or not
// count[10] --> counts frequency of digits which
// divide N
static int allDigits(String N)
{
// We initialize all digits of N as not divisible
// by N.
Boolean[] divide = new Boolean[10];
Arrays.fill(divide, Boolean.FALSE);
divide[1] = true; // 1 divides all numbers
// start checking divisibility of N by digits 2 to 9
for (int digit=2; digit<=9; digit++)
{
// if digit divides N then mark it as true
if (divisible(N, digit))
divide[digit] = true;
}
// Now traverse the number string to find and increment
// result whenever a digit divides N.
int result = 0;
for (int i=0; i<N.length(); i++)
{
if (divide[N.charAt(i)-'0'] == true)
result++;
}
return result;
}
// Driver program to run the case
public static void main(String args[])
{
String N = "122324";
System.out.println(allDigits(N));
}
}
// This code is contributed by Surendra_Gangwar
Python3
# Python3 program to find number of
# digits in N that divide N.
# Utility function to check
# divisibility by digit
def divisible(N, digit):
ans = 0;
for i in range(len(N)):
# (N[i]-'0') gives the digit
# value and form the number
ans = (ans * 10 + (ord(N[i]) - ord('0')));
ans %= digit;
return (ans == 0);
# Function to count digits which
# appears in N and divide N
# divide[10] --> array which tells
# that particular digit divides N or not
# count[10] --> counts frequency of
# digits which divide N
def allDigits(N):
# We initialize all digits of N
# as not divisible by N.
divide =[False]*10;
divide[1] = True; # 1 divides all numbers
# start checking divisibility of
# N by digits 2 to 9
for digit in range(2,10):
# if digit divides N then
# mark it as true
if (divisible(N, digit)):
divide[digit] = True;
# Now traverse the number string to
# find and increment result whenever
# a digit divides N.
result = 0;
for i in range(len(N)):
if (divide[(ord(N[i]) - ord('0'))] == True):
result+=1;
return result;
# Driver Code
N = "122324";
print(allDigits(N));
# This code is contributed by mits
C#
// C# program to find number of digits
// in N that divide N.
using System;
class GFG {
// Utility function to
// check divisibility by digit
static bool divisible(string N, int digit)
{
int ans = 0;
for (int i = 0; i < N.Length; i++)
{
// (N[i]-'0') gives the digit value and
// form the number
ans = (ans * 10 + (N[i] - '0'));
ans %= digit;
}
return (ans == 0);
}
// Function to count digits which
// appears in N and divide N
// divide[10] --> array which
// tells that particular
// digit divides N or not
// count[10] --> counts
// frequency of digits which
// divide N
static int allDigits(string N)
{
// We initialize all digits
// of N as not divisible by N
bool[] divide = new bool[10];
for (int i = 0; i < divide.Length; i++)
{
divide[i] = false;
}
// 1 divides all numbers
divide[1] = true;
// start checking divisibility
// of N by digits 2 to 9
for (int digit = 2; digit <= 9; digit++)
{
// if digit divides N
// then mark it as true
if (divisible(N, digit))
divide[digit] = true;
}
// Now traverse the number
// string to find and increment
// result whenever a digit divides N.
int result = 0;
for (int i = 0; i < N.Length; i++)
{
if (divide[N[i] - '0'] == true)
result++;
}
return result;
}
// Driver Code
public static void Main()
{
string N = "122324";
Console.Write(allDigits(N));
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
PHP
<?php
// PHP program to find number of
// digits in N that divide N.
// Utility function to check
// divisibility by digit
function divisible($N, $digit)
{
$ans = 0;
for ($i = 0; $i < strlen($N); $i++)
{
// (N[i]-'0') gives the digit
// value and form the number
$ans = ($ans * 10 + (int)($N[$i] - '0'));
$ans %= $digit;
}
return ($ans == 0);
}
// Function to count digits which
// appears in N and divide N
// divide[10] --> array which tells
// that particular digit divides N or not
// count[10] --> counts frequency of
// digits which divide N
function allDigits($N)
{
// We initialize all digits of N
// as not divisible by N.
$divide = array_fill(0, 10, false);
$divide[1] = true; // 1 divides all numbers
// start checking divisibility of
// N by digits 2 to 9
for ($digit = 2; $digit <= 9; $digit++)
{
// if digit divides N then
// mark it as true
if (divisible($N, $digit))
$divide[$digit] = true;
}
// Now traverse the number string to
// find and increment result whenever
// a digit divides N.
$result = 0;
for ($i = 0; $i < strlen($N); $i++)
{
if ($divide[(int)($N[$i] - '0')] == true)
$result++;
}
return $result;
}
// Driver Code
$N = "122324";
echo allDigits($N);
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript program to find number of digits
// in N that divide N.
// Utility function to
// check divisibility by digit
function divisible(N, digit)
{
let ans = 0;
for (let i = 0; i < N.length; i++)
{
// (N[i]-'0') gives the digit value and
// form the number
ans = (ans * 10 + (N[i] - '0'));
ans %= digit;
}
return (ans == 0);
}
// Function to count digits which
// appears in N and divide N
// divide[10] --> array which
// tells that particular
// digit divides N or not
// count[10] --> counts
// frequency of digits which
// divide N
function allDigits(N)
{
// We initialize all digits
// of N as not divisible by N
let divide = [];
for (let i = 0; i < divide.length; i++)
{
divide[i] = false;
}
// 1 divides all numbers
divide[1] = true;
// start checking divisibility
// of N by digits 2 to 9
for (let digit = 2; digit <= 9; digit++)
{
// if digit divides N
// then mark it as true
if (divisible(N, digit))
divide[digit] = true;
}
// Now traverse the number
// string to find and increment
// result whenever a digit divides N.
let result = 0;
for (let i = 0; i < N.length; i++)
{
if (divide[N[i] - '0'] == true)
result++;
}
return result;
}
// Driver Code
let N = "122324";
document.write(allDigits(N));
// This code is contributed by chinmoy1997pal.
</script>
Producción :
5
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@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