Comprobar si un número es divisible por 41 o no

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

Ejemplos:

Input : x  = 123
Output : Yes

Input : 104413920565933
Output : YES

Una solución al problema es extraer el último dígito y restar 4 veces el último dígito del 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 41, entonces el número dado es divisible por 41.
Enfoque:

Extraiga el último dígito del número/número truncado cada vez
Resta 4*(último dígito del número anterior) del número truncado
Repita los tres pasos anteriores todo el tiempo que sea necesario.

Ilustraciones:

Illustration 1:
30873-->3087-4*3=3075-->307-4*5=287-->28-4*7=0
As the remainder is zero, 30873 is divisible by 41

Illustration 2:
104413920565933 --> 10441392056593 - 4*3= 10441392056581
10441392056581 --> 1044139205658 - 4*1 = 1044139205654
1044139205654 --> 104413920565 - 4*4 = 104413920549
104413920549 --> 10441392054 - 4*9 = 10441392018
10441392018 --> 1044139201 - 4*8 = 1044139169
1044139169 --> 104413916 - 4*9 = 104413880
104413880 --> 10441388 - 4*0 = 10441380
10441388 --> 1044138 - 4*8 = 1044106
1044106 --> 104410 - 4*6 = 104386
104386 --> 10438 - 4*6 = 10414
10414 --> 1041 - 4*4 = 1025
1025 --> 102 - 4*5 =82
Now, 82%41 = 0 --> 82 is divisible by 41 and hence, 104413920565933 is divisible by 41

Prueba matemática :
Sea

$\overline{abc}$

Sea cualquier número tal que

$\overline{abc}$

=100a+10b+c.
Ahora suponga que

$\overline{abc}$

es divisible por 41. Entonces

$\overline{abc}\equiv$

0 (módulo 41)
100a+10b+c

$\equiv$

0 (módulo 41)
10(10a+b)+c

$\equiv$

0 (módulo 41)
10

$\overline{ab}$

+c

$\equiv$

0 (mod 41)
Ahora que hemos separado el último dígito del número, tenemos que encontrar una manera de usarlo.
Hacer el coeficiente de

$\overline{ab}$

1.
En otras palabras, tenemos que encontrar un número entero tal que n tal que 10n

$\equiv$

1 mod 41.
Se puede observar que el n más pequeño que satisface esta propiedad es -4 como -40

$\equiv$

1 mod 41.
Ahora podemos multiplicar la ecuación original 10

$\overline{ab}$

+c

$\equiv$

0 (mod 41)
por -4 y simplificarlo:
-40

$\overline{ab}$

-4c

$\equiv$

0 (módulo 41)

$\overline{ab}$

-4c

$\equiv$

0 (mod 41)
Hemos descubierto que si

$\overline{abc}\equiv$

0 (módulo 41) entonces,

$\overline{ab}$

-4c

$\equiv$

0 (módulo 41).
En otras palabras, para verificar si un número de 3 dígitos es divisible por 41,
podemos eliminar el último dígito, multiplicarlo por 4
y luego restarlo del resto de los dos dígitos.

A continuación se muestra la implementación del enfoque anterior:

C++

// CPP program to validate above logic
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the number
// is divisible by 41 or not
bool isDivisible(long long int n)
{
    while (n / 100)
    {
        // Extracting the last digit
        int d = n % 10;
 
        // Truncating the number
        n /= 10;
 
        // Subtracting the four times
        // the last digit from the
        // remaining number
        n -= d * 4;
    }
 
    // return true if number is divisible by 41
    return (n % 41 == 0);
}
 
int main()
{
    long long int n = 104413920565933;
    if (isDivisible(n))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Java

// Java program to validate above logic
 
class GFG {
 
// Function to check if the number
// is divisible by 41 or not
    static boolean isDivisible(long n) {
        while (n / 100 != 0) {
// Extracting the last digit
            int d = (int) (n % 10);
 
// Truncating the number
            n /= 10;
 
// Subtracting the four times
// the last digit from the
// remaining number
            n -= d * 4;
        }
 
// return true if number
// is divisible by 41
        return (n % 41 == 0);
    }
 
    public static void main(String[] args) {
        long n = 104413920565933L;
        if (isDivisible(n)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
 
    }
}
// This code is contributed by RAJPUT-JI

Python3

# Python3 Program to validate above logic
 
# Function to check if the number
# is divisible by 41 or not
def isDivisible(n) :
 
    while n // 100 :
 
        # Extracting the last digit
        d = n % 10
 
        # Truncating the number
        n //= 10
 
        # Subtracting the four times
        # the last digit from the 
        # remaining number
        n -= d * 4
 
    # return true if number is divisible by 41
    return n % 41 == 0
     
 
     
# Driver Code
if __name__ == "__main__" :
 
    n = 104413920565933
     
    if isDivisible(n) :
        print("Yes")
 
    else :
        print("No")
         
# This code is contributed by ANKITRAI1

C#

// C# program to validate above logic
using System;
 
class GFG
{
// Function to check if the number
// is divisible by 41 or not
static bool isDivisible(long n)
{
    while (n / 100 != 0)
    {
        // Extracting the last digit
        int d = (int)(n % 10);
 
        // Truncating the number
        n /= 10;
 
        // Subtracting the four times
        // the last digit from the
        // remaining number
        n -= d * 4;
    }
 
    // return true if number
    // is divisible by 41
    return (n % 41 == 0);
}
 
// Driver Code
static public void Main ()
{
    long n = 104413920565933;
    if (isDivisible(n))
        Console.Write("Yes");
    else
        Console.Write("No");
}
}
 
// This code is contributed by Raj

PHP

<?php
// PHP program to validate above logic
 
// Function to check if the number
// is divisible by 41 or not
function isDivisible($n)
{
    while ($n / 100)
    {
        // Extracting the last digit
        $d = $n % 10;
 
        // Truncating the number
        $n /= 10;
 
        // Subtracting the four times
        // the last digit from the
        // remaining number
        $n -= $d * 4;
    }
 
    // return true if number
    // is divisible by 41
    return ($n % 41 == 0);
}
 
// Driver Code
$n = 104413920565933;
if (isDivisible($n))
    echo "Yes"."\n";
else
    echo "No"."\n";
 
// This code is contributed
// by ChitraNayal
?>

Javascript

<script>
     
// JavaScript program to validate above logic
 
// Function to check if the number
// is divisible by 41 or not
     
    function isDivisible(n)
    {
        while (Math.floor(n / 100) != 0) {
// Extracting the last digit
            let d =  (n % 10);
  
// Truncating the number
            n = Math.floor(n/10);
  
// Subtracting the four times
// the last digit from the
// remaining number
            n -= d * 4;
        }
  
// return true if number
// is divisible by 41
        return (n % 41 == 0);
    }
     
    let n = 104413920565933;
        if (isDivisible(n)) {
            document.write("Yes");
        } else {
            document.write("No");
        }
     
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Producción:

Yes

Tenga en cuenta que el programa anterior puede no tener mucho sentido, ya que simplemente podría hacer n % 41 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.

Publicación traducida automáticamente

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

C++

Java

Python3

C#

PHP

Javascript

Deja una respuesta Cancelar la respuesta