Comprueba si algún número grande es divisible por 19 o no

Dado un número, la tarea es verificar rápidamente si el número es divisible por 19 o no. 
Ejemplos: 
 

Input : x = 38
Output : Yes

Input : x = 47
Output : No

Una solución al problema es extraer el último dígito y sumar 2 veces el último dígito al número restante y repetir este proceso hasta obtener un número de dos dígitos. Si el número de dos dígitos obtenido es divisible por 19, entonces el número dado es divisible por 19.
Enfoque: 
 

• Extraiga el último dígito del número/número truncado cada vez
• Añadir 2*(último dígito del número anterior) al número truncado
• Repita los tres pasos anteriores todo el tiempo que sea necesario.

Ilustración: 
 

101156-->10115+2*6 = 10127-->1012+2*7=1026-->102+2*6=114 and 114=6*19,
So 101156 is divisible by 19.

Prueba matemática: 
Sea  cualquier número tal que  =100a+10b+c. 
Ahora suponga que  es divisible por 19. Entonces 
0 (mod 19) 
100a+10b+c 0 (mod 19) 
10(10a+b)+c 0 (mod 19) 
10 +c 0 (mod 19)
Ahora que hemos separado el último dígito del número, tenemos que encontrar una manera de usarlo. 
Haz el coeficiente de  1. 
En otras palabras, tenemos que encontrar un entero tal que n tal que 10n 1 mod 19. 
Se puede observar que el n más pequeño que satisface esta propiedad es 2 como 20 1 mod 19. 
Ahora podemos multiplicar la ecuación original 10 +c 0 (mod 19) 
por 2 y simplificarlo: 
20 +2c 0 (mod 19) 
+2c 0 (mod 19) 
Hemos descubierto que si  0 (mod 19) entonces, 
+2c 0 (mod 19). 
En otras palabras, para verificar si un número de 3 dígitos es divisible por 19, 
podemos quitar el último dígito, multiplicarlo por 2 
y luego sumar el resto de los dos dígitos. 
 

// CPP Program to validate the above logic
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the number
// is divisible by 19 or not
bool isDivisible(long long int n)
{
 
    while (n / 100) //
    {
        // Extracting the last digit
        int d = n % 10;
 
        // Truncating the number
        n /= 10;
 
        // Adding twice the last digit
        // to the remaining number
        n += d * 2;
    }
 
    // return true if number is divisible by 19
    return (n % 19 == 0);
}
 
// Driver code
int main()
{
    long long int n = 101156;
    if (isDivisible(n))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

// Java Program to validate the above logic
import java.io.*;
 
class GFG {
 
// Function to check if the
// number is divisible by 19 or not
static boolean isDivisible(long n)
{
 
    while (n / 100>0)
    {
        // Extracting the last digit
        long d = n % 10;
 
        // Truncating the number
        n /= 10;
 
        // Subtracting the five times the
        // last digit from the remaining number
        n += d * 2;
    }
 
    // Return n is divisible by 19
    return (n % 19 == 0);
}
 
// Driver code
 
    public static void main (String[] args) {
    long n = 101156;
    if (isDivisible(n))
        System.out.println( "Yes");
    else
        System.out.println( "No");
    }
}
// This code is contributed by Raj.

// C# Program to validate the
// above logic
using System;
 
class GFG
{
     
// Function to check if the
// number is divisible by 19 or not
static bool isDivisible(long n)
{
 
    while (n / 100 > 0)
    {
        // Extracting the last digit
        long d = n % 10;
 
        // Truncating the number
        n /= 10;
 
        // Subtracting the five times
        // the last digit from the
        // remaining number
        n += d * 2;
    }
 
    // Return n is divisible by 19
    return (n % 19 == 0);
}
 
// Driver code
public static void Main()
{
    long n = 101156;
     
    if (isDivisible(n))
        Console.WriteLine( "Yes");
    else
        Console.WriteLine( "No");
}
}
 
// This code is contributed by ajit

<?php
// PHP Program to validate
// the above logic
 
// Function to check if the number
// is divisible by 19 or not
function isDivisible( $n)
{
     
    while (1)
    {
        // Extracting the last digit
        $d = $n % 10;
 
        // Truncating the number
        $n = $n / 10;
 
        // Adding twice the last digit
        // to the remaining number
        $n = $n + $d * 2;
        if($n < 100)
            break;
    }
     
    // return true if number is
    // divisible by 19
    return ($n % 19 == 0);
}
 
// Driver code
$n = 38;
 
if (isDivisible($n))
    echo "Yes" ;
else
    echo "No" ;
 
// This code is contributed by ash264
?>

<script>
 
// javascript Program to validate the above logic
 
// Function to check if the
// number is divisible by 19 or not
function isDivisible(n)
{
 
    while (parseInt(n / 100)>0)
    {
        // Extracting the last digit
        var d = n % 10;
 
        // Truncating the number
        n = parseInt(n/ 10);
 
        // Subtracting the five times the
        // last digit from the remaining number
        n += d * 2;
    }
 
    // Return n is divisible by 19
    return (n % 19 == 0);
}
 
// Driver code
var n = 101156;
if (isDivisible(n))
    document.write( "Yes");
else
    document.write( "No");
 
// This code is contributed by 29AjayKumar
 
</script>

Yes

Complejidad de tiempo: O(log ₁₀ n), tiempo requerido para verificar si el número es divisible por 19
Espacio auxiliar: O(1), ya que no se requiere espacio adicional

Tenga en cuenta que el programa anterior puede no tener mucho sentido, ya que simplemente podría hacer n % 19 para verificar la divisibilidad. La idea de este programa es validar el concepto. Además, este podría ser un enfoque eficiente si el número de entrada es grande y se proporciona como una string.