Comprueba si el gran número formado es divisible por 41 o no

Posted on by Rudeus Greyrat

Dados los dos primeros dígitos de un número grande digit1 y digit2 . También dado un número c y la longitud del número grande real. Los siguientes n-2 dígitos del número grande se calculan usando la fórmula dígito[i] = ( dígito[i – 1]*c + dígito[i – 2] ) % 10 . La tarea es verificar si el número formado es divisible por 41 o no. 
Ejemplos:
 

Input: digit1 = 1  , digit2 = 2  , c = 1  , n = 3
Output: YES
The number formed is 123
which is divisible by 41

Input: digit1 = 1  , digit2 = 4  , c = 6  , n = 3  
Output: NO

Un enfoque ingenuo es formar el número usando la fórmula dada. Comprueba si el número formado es divisible por 41 o no usando el operador %. Pero como el número es muy grande, no será posible almacenar un número tan grande. 
Enfoque eficiente: todos los dígitos se calculan usando la fórmula dada y luego se usa la propiedad asociativa de la multiplicación y la suma para verificar si es divisible por 41 o no. Un número es divisible por 41 o no significa (número % 41) es igual a 0 o no. 
Sea X el gran número así formado, que se puede escribir como. 
 

X = (dígito[0] * 10^n-1) + (dígito[1] * 10^n-2) + … + (dígito[n-1] * 10^0) 
X = ((((dígito[ 0] * 10 + dígito[1]) * 10 + dígito[2]) * 10 + dígito[3]) … ) * 10 + dígito[n-1] 
X % 41 = ((((((((dígito [0] * 10 + dígito[1]) % 41) * 10 + dígito[2]) % 41) * 10 + dígito[3]) % 41) … ) * 10 + dígito[n-1]) % 41

 
Por lo tanto, después de calcular todos los dígitos, se sigue el siguiente algoritmo: 
 

  1. Inicializa el primer dígito a ans .
  2. Iterar para todos los dígitos n-1.
  3. Calcule ans en cada i -ésimo paso por (ans * 10 + digit[i]) % 41 usando la propiedad asociativa.
  4. Compruebe el valor final de ans si es divisible por 41 r no.

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

C++

// C++ program to check a large number
// divisible by 41 or not
#include <bits/stdc++.h>
using namespace std;
 
// Check if a number is divisible by 41 or not
bool DivisibleBy41(int first, int second, int c, int n)
{
    // array to store all the digits
    int digit[n];
 
    // base values
    digit[0] = first;
    digit[1] = second;
 
    // calculate remaining digits
    for (int i = 2; i < n; i++)
        digit[i] = (digit[i - 1] * c + digit[i - 2]) % 10;
 
    // calculate answer
    int ans = digit[0];
    for (int i = 1; i < n; i++)
        ans = (ans * 10 + digit[i]) % 41;
 
    // check for divisibility
    if (ans % 41 == 0)
        return true;
    else
        return false;
}
 
// Driver Code
int main()
{
 
    int first = 1, second = 2, c = 1, n = 3;
 
    if (DivisibleBy41(first, second, c, n))
        cout << "YES";
    else
        cout << "NO";
    return 0;
}

C

// C program to check a large number
// divisible by 41 or not
#include <stdio.h>
#include <stdbool.h>
 
// Check if a number is divisible by 41 or not
bool DivisibleBy41(int first, int second, int c, int n)
{
    // array to store all the digits
    int digit[n];
 
    // base values
    digit[0] = first;
    digit[1] = second;
 
    // calculate remaining digits
    for (int i = 2; i < n; i++)
        digit[i] = (digit[i - 1] * c + digit[i - 2]) % 10;
 
    // calculate answer
    int ans = digit[0];
    for (int i = 1; i < n; i++)
        ans = (ans * 10 + digit[i]) % 41;
 
    // check for divisibility
    if (ans % 41 == 0)
        return true;
    else
        return false;
}
 
// Driver Code
int main()
{
 
    int first = 1, second = 2, c = 1, n = 3;
 
    if (DivisibleBy41(first, second, c, n))
        printf("YES");
    else
        printf("NO");
    return 0;
}
 
// This code is contributed by kothavvsaakash.

Java

// Java program to check
// a large number divisible
// by 41 or not
import java.io.*;
 
class GFG
{
// Check if a number is
// divisible by 41 or not
static boolean DivisibleBy41(int first,
                             int second,
                             int c, int n)
{
    // array to store
    // all the digits
    int digit[] = new int[n];
 
    // base values
    digit[0] = first;
    digit[1] = second;
 
    // calculate remaining
    // digits
    for (int i = 2; i < n; i++)
        digit[i] = (digit[i - 1] * c +
                    digit[i - 2]) % 10;
 
    // calculate answer
    int ans = digit[0];
    for (int i = 1; i < n; i++)
        ans = (ans * 10 +
               digit[i]) % 41;
 
    // check for
    // divisibility
    if (ans % 41 == 0)
        return true;
    else
        return false;
}
 
// Driver Code
public static void main (String[] args)
{
    int first = 1, second = 2, c = 1, n = 3;
 
    if (DivisibleBy41(first, second, c, n))
        System.out.println("YES");
    else
        System.out.println("NO");
}
}
 
// This code is contributed
// by akt_mit

Python3

# Python3 program to check
# a large number divisible
# by 41 or not
 
# Check if a number is
# divisible by 41 or not
def DivisibleBy41(first,
                  second, c, n):
 
    # array to store
    # all the digits
    digit = [0] * n
 
    # base values
    digit[0] = first
    digit[1] = second
 
    # calculate remaining
    # digits
    for i in range(2,n):
        digit[i] = (digit[i - 1] * c +
                    digit[i - 2]) % 10
 
    # calculate answer
    ans = digit[0]
    for i in range(1,n):
        ans = (ans * 10 + digit[i]) % 41
 
    # check for
    # divisibility
    if (ans % 41 == 0):
        return True
    else:
        return False
 
# Driver Code
first = 1
second = 2
c = 1
n = 3
 
if (DivisibleBy41(first,
                  second, c, n)):
    print("YES")
else:
    print("NO")
 
# This code is contributed
# by Smita

C#

// C# program to check
// a large number divisible
// by 41 or not
using System;
 
class GFG
{
     
// Check if a number is
// divisible by 41 or not
static bool DivisibleBy41(int first,
                          int second,
                          int c, int n)
{
    // array to store
    // all the digits
    int []digit = new int[n];
 
    // base values
    digit[0] = first;
    digit[1] = second;
 
    // calculate
    // remaining
    // digits
    for (int i = 2; i < n; i++)
        digit[i] = (digit[i - 1] * c +
                    digit[i - 2]) % 10;
 
    // calculate answer
    int ans = digit[0];
    for (int i = 1; i < n; i++)
        ans = (ans * 10 +
            digit[i]) % 41;
 
    // check for
    // divisibility
    if (ans % 41 == 0)
        return true;
    else
        return false;
}
 
// Driver Code
public static void Main ()
{
    int first = 1,
        second = 2,
        c = 1, n = 3;
 
    if (DivisibleBy41(first, second, c, n))
        Console.Write("YES");
    else
        Console.Write("NO");
}
}
 
// This code is contributed
// by Smita

PHP

<?php
// PHP program to check a
// large number divisible
// by 41 or not
 
// Check if a number is
// divisible by 41 or not
function DivisibleBy41($first, $second, $c, $n)
{
    // array to store
    // all the digits
    $digit[$n] = range(1, $n);
 
    // base values
    $digit[0] = $first;
    $digit[1] = $second;
 
    // calculate remaining digits
    for ($i = 2; $i < $n; $i++)
        $digit[$i] = ($digit[$i - 1] * $c +
                      $digit[$i - 2]) % 10;
 
    // calculate answer
    $ans = $digit[0];
    for ($i = 1; $i < $n; $i++)
        $ans = ($ans * 10 + $digit[$i]) % 41;
 
    // check for divisibility
    if ($ans % 41 == 0)
        return true;
    else
        return false;
}
 
// Driver Code
$first = 1;
$second = 2;
$c = 1;
$n = 3;
 
if (DivisibleBy41($first, $second, $c, $n))
    echo "YES";
else
    echo "NO";
 
// This code is contributed by Mahadev.
?>

Javascript

<script>
 
// Javascript program to check
// a large number divisible
// by 41 or not
 
// Check if a number is
// divisible by 41 or not
function DivisibleBy41(first, second,  c, n)
{
    // array to store
    // all the digits
    let digit = new Array(n).fill(0);
   
    // base values
    digit[0] = first;
    digit[1] = second;
   
    // calculate remaining
    // digits
    for (let i = 2; i < n; i++)
        digit[i] = (digit[i - 1] * c +
                    digit[i - 2]) % 10;
   
    // calculate answer
    let ans = digit[0];
    for (let i = 1; i < n; i++)
        ans = (ans * 10 +
               digit[i]) % 41;
   
    // check for
    // divisibility
    if (ans % 41 == 0)
        return true;
    else
        return false;
}
     
// driver program
     
    let first = 1, second = 2, c = 1, n = 3;
   
    if (DivisibleBy41(first, second, c, n))
        document.write("YES");
    else
        document.write("NO");
  
 // This code is contributed by susmitakundugoaldanga.
</script>
Producción: 

YES

 

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)
 

Publicación traducida automáticamente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *