Se le da un número grande de n dígitos, debe verificar si es divisible por 999 sin dividir o encontrar el módulo del número por 999.
Ejemplos:
Input : 235764 Output : Yes Input : 23576 Output : No
Dado que el número de entrada puede ser muy grande, no podemos usar n % 999 para verificar si un número es divisible por 999 o no, especialmente en lenguajes como C/C++. La idea se basa en el siguiente hecho.
Las soluciones se basan en el siguiente hecho.
Un número es divisible por 999 si la suma de sus grupos de 3 dígitos (si los grupos requeridos se forman agregando 0 al principio) es divisible por 999.
Ilustración:
Input : 235764
Output : Yes
Explanation : Step I - read input : 235, 764
Step II - 235 + 764 = 999
As result is 999 then we can
conclude that it is divisible by 999.
Input : 1244633121
Output : Yes
Explanation : Step I - read input : 1, 244, 633, 121
Step II - 001 + 244 + 633 + 121 = 999
As result is 999 then we can conclude
that it is divisible by 999.
Input : 999999999
Output : Yes
Explanation : Step I - read input : 999, 999, 999
Step II - 999 + 999 + 999 = 2997
Step III - 997 + 002 = 999
As result is 999 then we can conclude
that it is divisible by 999.
¿Como funciona esto?
Let us consider 235764, we can write it as
235764 = 2*105 + 3*104 + 5*103 +
7*102 + 6*10 + 4
The idea is based on below observation:
Remainder of 103 divided by 999 is 1
For i > 3, 10i % 999 = 10i-3 % 999
Let us see how we use above fact.
Remainder of 2*105 + 3*104 + 5*103 +
7*102 + 6*10 + 4
Remainder with 999 can be written as :
2*100 + 3*10 + 5*1 + 7*100 + 6*10 + 4
The above expression is basically sum of
groups of size 3.
Since the sum is divisible by 999, answer is yes.
Un método simple y eficiente es tomar la entrada en forma de string (haga su longitud en forma de 3*m agregando 0 a la izquierda del número si es necesario) y luego debe agregar los dígitos en bloques de tres de derecha a izquierda hasta se convierte en un número de 3 dígitos y si ese resultado es 999 podemos decir que ese número es divisible por 999.
Como en el caso de «divisibilidad por 9» verificamos que la suma de todos los dígitos es divisible por 9 o no, lo mismo ocurre en el caso de divisibilidad por 999. Sumamos todos los grupos de 3 dígitos de derecha a izquierda y verificamos si el resultado final es 999 o no.
Implementación:
C++
// CPP for divisibility of number by 999
#include<bits/stdc++.h>
using namespace std;
// function to check divisibility
bool isDivisible999(string num)
{
int n = num.length();
if (n == 0 && num[0] == '0')
return true;
// Append required 0s at the beginning.
if (n % 3 == 1)
num = "00" + num;
if (n % 3 == 2)
num = "0" + num;
// add digits in group of three in gSum
int gSum = 0;
for (int i = 0; i<n; i++)
{
// group saves 3-digit group
int group = 0;
group += (num[i++] - '0') * 100;
group += (num[i++] - '0') * 10;
group += num[i] - '0';
gSum += group;
}
// calculate result till 3 digit sum
if (gSum > 1000)
{
num = to_string(gSum);
n = num.length();
gSum = isDivisible999(num);
}
return (gSum == 999);
}
// driver program
int main()
{
string num = "1998";
int n = num.length();
if (isDivisible999(num))
cout << "Divisible";
else
cout << "Not divisible";
return 0;
}
Java
//Java for divisibility of number by 999
class Test
{
// Method to check divisibility
static boolean isDivisible999(String num)
{
int n = num.length();
if (n == 0 && num.charAt(0) == '0')
return true;
// Append required 0s at the beginning.
if (n % 3 == 1)
num = "00" + num;
if (n % 3 == 2)
num = "0" + num;
// add digits in group of three in gSum
int gSum = 0;
for (int i = 0; i<n; i++)
{
// group saves 3-digit group
int group = 0;
group += (num.charAt(i++) - '0') * 100;
group += (num.charAt(i++) - '0') * 10;
group += num.charAt(i) - '0';
gSum += group;
}
// calculate result till 3 digit sum
if (gSum > 1000)
{
num = Integer.toString(gSum);
n = num.length();
gSum = isDivisible999(num) ? 1 : 0;
}
return (gSum == 999);
}
// Driver method
public static void main(String args[])
{
String num = "1998";
System.out.println(isDivisible999(num) ? "Divisible" : "Not divisible");
}
}
Python 3
# Python3 program for divisibility
# of number by 999
# function to check divisibility
def isDivisible999(num):
n = len(num);
if(n == 0 or num[0] == '0'):
return true
# Append required 0s at the beginning.
if((n % 3) == 1):
num = "00" + num
if((n % 3) == 2):
num = "0" + num
# add digits in group of three in gSum
gSum = 0
for i in range(0, n, 3):
# group saves 3-digit group
group = 0
group += (ord(num[i]) - 48) * 100
group += (ord(num[i + 1]) - 48) * 10
group += (ord(num[i + 2]) - 48)
gSum += group
# calculate result till 3 digit sum
if(gSum > 1000):
num = str(gSum)
n = len(num)
gSum = isDivisible999(num)
return (gSum == 999)
# Driver code
if __name__=="__main__":
num = "1998"
n = len(num)
if(isDivisible999(num)):
print("Divisible")
else:
print("Not divisible")
# This code is contributed
# by Sairahul Jella
C#
// C# code for divisibility of number by 999
using System;
class Test
{
// Method to check divisibility
static bool isDivisible999(String num)
{
int n = num.Length;
if (n == 0 && num[0] == '0')
return true;
// Append required 0s at the beginning.
if (n % 3 == 1)
num = "00" + num;
if (n % 3 == 2)
num = "0" + num;
// add digits in group of three in gSum
int gSum = 0;
for (int i = 0; i<n; i++)
{
// group saves 3-digit group
int group = 0;
group += (num[i++] - '0') * 100;
group += (num[i++] - '0') * 10;
group += num[i] - '0';
gSum += group;
}
// calculate result till 3 digit sum
if (gSum > 1000)
{
num = Convert.ToString(gSum);
n = num.Length ;
gSum = isDivisible999(num) ? 1 : 0;
}
return (gSum == 999);
}
// Driver method
public static void Main()
{
String num = "1998";
Console.WriteLine(isDivisible999(num) ? "Divisible" : "Not divisible");
}
// This code is contributed by Ryuga
}
PHP
<?php
// PHP for divisibility of number by 999
// function to check divisibility
function isDivisible999($num)
{
$n = strlen($num);
if ($n == 0 && $num[0] == '0')
return true;
// Append required 0s at the beginning.
if ($n % 3 == 1)
$num = "00" . $num;
if ($n % 3 == 2)
$num = "0" . $num;
// add digits in group of three in gSum
$gSum = 0;
for ($i = 0; $i < $n; $i += 3)
{
// group saves 3-digit group
$group = 0;
$group += (ord($num[$i]) - 48) * 100;
$group += (ord($num[$i + 1]) - 48) * 10;
$group += (ord($num[$i + 2]) - 48);
$gSum += $group;
}
// calculate result till 3 digit sum
if ($gSum > 1000)
{
$num = strval($gSum);
$n = strlen($num);
$gSum = isDivisible999($num);
}
return ($gSum == 999);
}
// Driver Code
$num = "1998";
if (isDivisible999($num))
echo "Divisible";
else
echo "Not divisible";
// This code is contributed by mits
?>
Javascript
<script>
// Javascript for divisibility of number by 999
// function to check divisibility
function isDivisible999(num)
{
let n = num.length;
if (n == 0 && num[0] == '0')
return true;
// Append required 0s at the beginning.
if (n % 3 == 1)
num = "00" + num;
if (n % 3 == 2)
num = "0" + num;
// add digits in group of three in gSum
let gSum = 0;
for (let i = 0; i < n; i += 3)
{
// group saves 3-digit group
group = 0;
group += (num.charCodeAt(i) - 48) * 100;
group += (num.charCodeAt(i + 1) - 48) * 10;
group += (num.charCodeAt(i + 2) - 48);
gSum += group;
}
// calculate result till 3 digit sum
if (gSum > 1000)
{
num = String(gSum);
n = strlen(num);
gSum = isDivisible999(num);
}
return (gSum == 999);
}
// Driver Code
let num = "1998";
if (isDivisible999(num))
document.write("Divisible");
else
document.write("Not divisible");
// This code is contributed by _saurabh_jaiswal.
</script>
Divisible
Complejidad temporal : O(n)
Espacio auxiliar : O(1)
Método: Comprobación de que cualquier número dado es divisible por 999 o no mediante el operador de división de módulo «%».
Implementación:
Python3
# Python code
# To check whether the given number is divisible by 999 or not
#input
n=235764
# the above input can also be given as n=input() -> taking input from user
# finding given number is divisible by 999 or not
if int(n)%999==0:
print("Yes")
else:
print("No")
# this code is contributed by gangarajula laxmi
Javascript
<script>
// JavaScript code for the above approach
//input
let n = 235764
// the above input can also be given as n=input() -> taking input from user
// finding given number is divisible by 999 or not
if (n % 999 == 0)
document.write("Yes")
else
document.write("No")
// This code is contributed by Potta Lokesh
</script>
Yes
Complejidad de tiempo: O(log(n)) , para números pequeños.
Para números enteros grandes, la división de Python (y el módulo) usan un algoritmo O(n^2). La multiplicación usa la multiplicación de Karatsuba que es O(n^1.585) pero la división usa la división básica de «escuela primaria».
Espacio Auxiliar : O(1)
Más algoritmos de divisibilidad .
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . 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.
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