Divisible por 37 para números grandes

Dado un gran número n, necesitamos comprobar si es divisible por 37. Imprime verdadero si es divisible por 37, de lo contrario es falso.
Ejemplos: 
 

Input  : 74
Output : True

Input : 73
Output : False

Input : 8955795758 (10 digit number)
Output : True

Un número m de r dígitos cuya forma digital es (ar-1 ar-2….a2 a1 a0) es divisible por 37 si y solo si la suma de la serie de números (a2 a1 a0) + (a5 a4 a3) + (a8 a7 a6) + … es divisible por 37. Los tripletes de dígitos entre paréntesis representan un número de 3 dígitos en forma digital.
 

El número dado n se puede escribir como una suma de potencias de 1000 de la siguiente manera. 
n = (a2 a1 a0) + (a5 a4 a3)*1000 + (a8 a7 a6)*(1000*1000) +…. 
Como 1000 = (1)(mod 37), 1000 según relación de congruencia. 
Para un entero positivo n, se dice que dos números a y b son congruentes módulo n, si su diferencia 
(a – b) es un múltiplo entero de n (es decir, si hay un entero k tal que a – b = kn ). Esta relación de congruencia normalmente se considera cuando a y b son números enteros, y se denota

. Por lo tanto, podemos escribir: 
n = { (a2a1a0) + (a5a4a3)* (1) + (a8a7a6)* (1)*(1)+…. .}(mod 37), 
Por lo tanto, n es divisible por 37 si y solo si la serie es divisible por 37.

Ejemplos: 
 

Input : 8955795758 (10 digit number)
Output : True
Explanation:
     We express the number in terms of 
     triplets of digits as follows.
     (008)(955)(795)(758)
     Now, 758 + 795 + 955 + 8 = 2516
     For 2516, the triplets will be:
     (002)(516)
     Now 516 + 2 = 518 which is divisible 
     by 37. Hence the number is divisible 
     by 37.

Input : 189710809179199 (15 digit number)
Output : False

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 para formar una serie. Calcular la suma de la serie. Si la suma de la serie tiene más de 3 dígitos, nuevamente llama recursivamente a esta función. 
Finalmente comprueba si la suma resultante es divisible por 37 o no.
Aquí está la implementación del programa para verificar la divisibilidad por 37.
 

// CPP program for checking divisibility by 37
// function divisible37 which returns True if
// number is divisible by 37 otherwise False
#include <bits/stdc++.h>
using namespace std;
 
int divisibleby37(string n){
    int l = n.length();
    if (n == "0")
        return 0;
 
    // Append required 0's at the beginning
    if (l % 3 == 1){
        n = "00"+ n;
        l += 2;
    }
    else if (l % 3 == 2){
        n = "0"+ n;
        l += 1;
    }
     
    int gSum = 0;
     
    while (l != 0){
 
    // group saves 3-digit group
    string group = n.substr(l - 3, l);
        l = l - 3;
    int gvalue = (group[0] - '0') * 100 +
                 (group[1] - '0') * 10 +
                 (group[2] - '0') * 1;
                  
    // add the series
    gSum = gSum + gvalue;
    }
     
    // if sum of series gSum has minimum 4
    // digits in it, then again recursive
    // call divisibleby37 function
    if (gSum >= 1000)
        return (divisibleby37(to_string(gSum)));
    else
        return (gSum % 37 == 0);
 
}
 
// drive program to test the above function
int main(){
 
    string s="8955795758";
     
    if (divisibleby37(s))
    cout<<"True";
    else
    cout<<"False";
    return 0;
}
// This code is contributed by Prerna Saini

// Java program for checking
// divisibility by 37
 
class GFG
{
// function divisible37 which
// returns True if number is
// divisible by 37 otherwise False
static int divisibleby37(String n1)
{
    int l = n1.length();
    if (n1 == "0")
        return 0;
 
    // Append required 0's
    // at the beginning
    if (l % 3 == 1)
    {
        n1 = "00"+ n1;
        l += 2;
    }
    else if (l % 3 == 2)
    {
        n1 = "0"+ n1;
        l += 1;
    }
    char[]  n= n1.toCharArray();
    int gSum = 0;
    while (l != 0)
    {
 
    // group saves 3-digit group
    int gvalue;
    if(l == 2)
        gvalue = ((int)n[(l - 2)] - 48) * 100 +
                ((int)n[(l - 1)] - 48) * 10;
    else if(l == 1)
        gvalue = ((int)n[(l - 1)] - 48) * 100;
    else
        gvalue = ((int)n[(l - 3)] - 48) * 100 +
                ((int)n[(l - 2)] - 48) * 10 +
                ((int)n[(l - 1)] - 48) * 1;
    l = l - 3;
     
    // add the series
    gSum = gSum + gvalue;
    }
     
    // if sum of series gSum has minimum 4
    // digits in it, then again recursive
    // call divisibleby37 function
    if (gSum >= 1000)
        return (divisibleby37(String.valueOf(gSum)));
    else
        return (gSum % 37 == 0) ? 1 : 0;
 
}
 
// Driver Code
public static void main(String[] args)
{
    String s="8955795758";
     
    if (divisibleby37(s) == 1)
    System.out.println("True");
    else
    System.out.println("False");
}
}
 
// This code is contributed by mits

# Python code for checking divisibility by 37
# function divisible37 which returns True if
# number is divisible by 37 otherwise False
def divisibleby37(n):
    l = len(n)
    if (n == 0):
        return True
   
    # Append required 0's at the beginning
    if (l%3 == 1):
        n = "00"+ n
        l += 2
    elif (l%3 == 2):
        n = "0"+ n
        l += 1
 
    gSum = 0
    while (l != 0):
 
        # group saves 3-digit group
        group = int(n[l-3:l])
        l = l-3
 
        # add the series
        gSum = gSum + group
 
    # if sum of series gSum has minimum 4
    # digits in it, then again recursive
    # call divisibleby37 function
    if (gSum >= 1000):
        return(divisibleby37(str(gSum)))
    else:
        return (gSum%37==0)
 
# Driver method to test the above function
print(divisibleby37("8955795758"))

// C# program for checking
// divisibility by 37
using System;
 
class GFG
{
// function divisible37 which
// returns True if number is
// divisible by 37 otherwise False
static int divisibleby37(string n)
{
    int l = n.Length;
    if (n == "0")
        return 0;
 
    // Append required 0's
    // at the beginning
    if (l % 3 == 1)
    {
        n = "00"+ n;
        l += 2;
    }
    else if (l % 3 == 2)
    {
        n = "0"+ n;
        l += 1;
    }
     
    int gSum = 0;
    while (l != 0)
    {
 
    // group saves 3-digit group
    int gvalue;
    if(l == 2)
        gvalue = ((int)n[(l - 2)] - 48) * 100 +
                 ((int)n[(l - 1)] - 48) * 10;
    else if(l == 1)
        gvalue = ((int)n[(l - 1)] - 48) * 100;
    else
        gvalue = ((int)n[(l - 3)] - 48) * 100 +
                 ((int)n[(l - 2)] - 48) * 10 +
                 ((int)n[(l - 1)] - 48) * 1;
    l = l - 3;
     
    // add the series
    gSum = gSum + gvalue;
    }
     
    // if sum of series gSum has minimum 4
    // digits in it, then again recursive
    // call divisibleby37 function
    if (gSum >= 1000)
        return (divisibleby37(gSum.ToString()));
    else
        return (gSum % 37 == 0) ? 1 : 0;
 
}
 
// Driver Code
public static void Main()
{
    string s="8955795758";
     
    if (divisibleby37(s) == 1)
    Console.WriteLine("True");
    else
    Console.WriteLine("False");
}
}
 
// This code is contributed by mits

<?php
// PHP program for checking
// divisibility by 37
 
// function divisible37 which
// returns True if number is
// divisible by 37 otherwise
// False
function divisibleby37($n)
{
    $l = strlen($n);
    if ($n == '0')
        return 0;
 
    // Append required 0's
    // at the beginning
    if ($l % 3 == 1)
    {
        $n = "00" . $n;
        $l += 2;
    }
    else if ($l % 3 == 2)
    {
        $n = "0" . $n;
        $l += 1;
    }
     
    $gSum = 0;
     
    while ($l != 0)
    {
 
    // group saves 3-digit group
    $group = substr($n,$l - 3, $l);
        $l = $l - 3;
    $gvalue = (ord($group[0]) - 48) * 100 +
              (ord($group[1]) - 48) * 10 +
              (ord($group[2]) - 48) * 1;
                 
    // add the series
    $gSum = $gSum + $gvalue;
    }
     
    // if sum of series gSum has
    // minimum 4 digits in it,
    // then again recursive call
    // divisibleby37 function
    if ($gSum >= 1000)
        return (divisibleby37((string)($gSum)));
    else
        return ($gSum % 37 == 0);
 
}
 
// Driver code
$s = "8955795758";
 
if (divisibleby37($s))
echo "True";
else
echo "False";
 
// This code is contributed
// by mits
?>

<script>
// Javascript program for checking
// divisibility by 37
 
// function divisible37 which
// returns True if number is
// divisible by 37 otherwise
// False
function divisibleby37(n)
{
    let l = n.length;
    if (n == '0')
        return 0;
 
    // Append required 0's
    // at the beginning
    if (l % 3 == 1)
    {
        n = "00" + n;
        l += 2;
    }
    else if (l % 3 == 2)
    {
        n = "0" + n;
        l += 1;
    }
     
    let gSum = 0;
     
    while (l != 0)
    {
 
    // group saves 3-digit group
    let group = n.substr(l - 3, l);
        l = l - 3;
    gvalue = (group.charCodeAt(0) - 48) * 100 +
             (group.charCodeAt(1) - 48) * 10 +
             (group.charCodeAt(2) - 48) * 1;
                 
    // add the series
    gSum = gSum + gvalue;
    }
     
    // if sum of series gSum has
    // minimum 4 digits in it,
    // then again recursive call
    // divisibleby37 function
    if (gSum >= 1000)
        return (divisibleby37(`${gSum}`));
    else
        return (gSum % 37 == 0);
 
}
 
// Driver code
let s = "8955795758";
 
if (divisibleby37(s))
    document.write("True");
else
    document.write("False");
 
// This code is contributed
// by _saurabh_jaiswal.
</script>

True

Complejidad de tiempo: O(n), donde n es la longitud de la string.

Espacio Auxiliar: O(1)

Método: Comprobación de que el número dado es divisible por 37 o no utilizando el operador de división de módulo «%».

// C++ code To check whether the given number is divisible
// by 37 or not
 
#include <iostream>
using namespace std;
 
int main()
{
 
    // input number
    int num = 8955;
    // checking if the given number is divisible by 37 or
    // not using modulo division operator if the output of
    // num%37 is equal to 0 then given number is divisible
    // by 37 otherwise not divisible by 37
    if (num % 37 == 0) {
        cout << " divisible";
    }
    else {
        cout << " not divisible";
    }
    return 0;
}

// Java code To check whether the given number is divisible
// by 37 or not
import java.util.*;
 
class GFG
{
  public static void main(String[] args)
  {
 
    // input number
    int num = 8955;
 
    // checking if the given number is divisible by 37 or
    // not using modulo division operator if the output of
    // num%37 is equal to 0 then given number is divisible
    // by 37 otherwise not divisible by 37
    if (num % 37 == 0) {
      System.out.println(" divisible");
    }
    else {
      System.out.println(" not divisible");
    }
  }
}
 
// This code is contributed by phasing17

# Python code
# To check whether the given number is divisible by 37 or not
 
#input
n=8955795758
# the above input can also be given as n=input() -> taking input from user
# finding given number is divisible by 37 or not
if int(n)%37==0:
  print("true")
else:
  print("false")
   
  # this code is contributed by gangarajula laxmi

using System;
 
public class GFG {
 
    static public void Main()
    {
 
        // input number
        long num = 8955795758;
 
    // checking if the given number is divisible by 37 or
    // not using modulo division operator if the output of
    // num%37 is equal to 0 then given number is divisible
    // by 37 otherwise not divisible by 37
        if (num % 37 == 0) {
            Console.Write("Yes");
        }
        else {
            Console.Write("No");
        }
    }
}
 
// This code is contributed by laxmigangarajula03

<script>
        // JavaScript code for the above approach
        // To check whether the given number is divisible by 37 or not
  
        // input
        var n = 8955795758
         
        // finding given number is divisible by 37 or not
        if (n % 37 == 0)
            document.write("true")
        else
            document.write("false")
  
 // This code is contributed by laxmigangarajula03
    </script>

true

Este artículo es una contribución de Sruti Rai . 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.