Divisibilidad por 3 donde cada dígito es la suma de todos los dígitos del prefijo módulo 10

Posted on by Rudeus Greyrat

Dado K, número de dígitos, y d0 y d1 como los dos dígitos para formar el número entero de tamaño k. La tarea es verificar si el número de tamaño k formado usando d0 y d1 es divisible por 3 o no. 
Para cada i, d i es la suma de todos los dígitos anteriores (más significativos), módulo 10; más formalmente, debe cumplirse la siguiente fórmula: 
\huge{d_{i} = \sum_{j = 0}^{i - 1}d_{j} (mod 10), 2 \leqslant i < k}
Ejemplos: 
 

Input : K = 5 d0 = 3 d1 = 4
Output : NO
Explanation : 
The whole number N is 34748 (Starting from 
third digit, every digit is some of preceding
digits mod 10). Since 34748 is not divisible 
by 3, answer is NO.

Input : K = 13 d0 = 8 d1 = 1
Output : YES
Explanation :
The whole number N is 8198624862486, 
which is divisible by 3, so the answer
is YES.

K puede ser muy largo, por lo que generar el número completo, calcular la suma de los dígitos y luego verificar el múltiplo de 3 es engorroso. La idea clave detrás de la solución es que los dígitos comienzan a repetirse después de un tiempo en un ciclo de longitud 4 y luego la suma de los dígitos se puede determinar en el paso O(1). 
Conocemos d0 y d1, 
entonces, d2 = (d0 + d1) mod 10 
d3 = (d2 + d1 + d0) mod 10 = ((d0 + d1) mod 10 + (d0 + d1)) mod 10 = 2 * ( d0 + d1) mod 10 
d4 = (d3 + d2 + d1 + d0) mod 10 = 4 * (d0 + d1) mod 10 
d5 = (d4 + d3 + d2 + d1 + d0) mod 10 = 8 * (d0 + d1) mod 10 
d6 = (d5 +…+ d1 + d0) mod 10 = 16 * (d0 + d1) mod 10 = 6 * (d0 + d1) mod 10 
d7 = (d6 ++…+ d1 + d0) mod 10 = 32 * (d0 + d1) mod 10 = 2 * (d0 + d1) mod 10
Si seguimos obteniendo di, veremos que la resultante simplemente recorre los mismos valores. Podemos ver que (d0 + d1) contribuye 1 vez(es) a d2, 2 veces a d3, 4 veces a d4, 8 veces a d5, …, 2^(k – 2) veces a dk .
Pero, dado que las potencias de 2 bajo módulo 10 ciclan de 1, 2, 4, 8, 6, 2, 4. Aquí, la duración del ciclo es de 4, donde d2 no está presente en el ciclo. Sea, S = (2 * (d0 + d1)) mod 10 + (4 * (d0 + d1)) mod 10 + (8 * (d0 + d1)) mod 10 + (6 * (d0 + d1)) mod 10, este es el ciclo que se repite.
Entonces, la suma de dígitos = (d0 + d1 + d2) + S * ((k – 3) / 4) + x . Aquí, los primeros 3 términos serán cubiertos por d0, d1, d2 y luego los grupos de 4 serán cubiertos por S, pero esta fórmula todavía no ha sumado algunos términos al final. Ese es el residuo que está anotado por x .
A continuación se muestra la implementación del enfoque anterior:
 

C++

// CPP code to check divisibility by 3
#include <bits/stdc++.h>
using namespace std;
 
// Function to check the divisibility
string check(long int k, int d0, int d1)
{
 
    // Cycle
    long int s = (2 * (d0 + d1)) % 10 +
                 (4 * (d0 + d1)) % 10 +
                 (8 * (d0 + d1)) % 10 +
                 (6 * (d0 + d1)) % 10;
     
    // no of residual terms
    int a = (k - 3) % 4;
     
    // sum of residual terms
    int x;
     
    switch(a)
    {
     
        // if no of residue term = 0
        case 0:
     
        x = 0;
        break;
     
        // if no of residue term = 1
        case 1:
     
        x = (2 * (d0 + d1)) % 10;
        break;
 
        // if no of residue term = 2
        case 2:
     
        x = (2 * (d0 + d1)) % 10 +
            (4 * (d0 + d1)) % 10;
        break;
     
        // if no of residue term = 3
        case 3:
     
        x = (2 * (d0 + d1)) % 10 +
            (4 * (d0 + d1)) % 10 +
            (8 * (d0 + d1)) % 10;
         
        break;
    }
     
    // sum of all digits
    long int sum = d0 + d1 + ((k - 3) / 4) * s + x;
     
    // divisibility check
    if(sum % 3 == 0)
        return "YES";
    return "NO";
}
 
// Driver code
int main()
{
 
    long int k, d0, d1;
     
    k = 13;
    d0 = 8;
    d1 = 1;
     
    cout << check(k, d0, d1) << endl;
         
    k = 5;
    d0 = 3;
    d1 = 4;
         
    cout << check(k, d0, d1) << endl;
 
    return 0;
}

Java

// Java code to check divisibility by 3
 
import java.util.*;
import java.io.*;
 
class GFG {
    // Function to check the divisibility
static String check( int k, int d0, int d1)
{
 
    // Cycle
     int s = (2 * (d0 + d1)) % 10 +
                (4 * (d0 + d1)) % 10 +
                (8 * (d0 + d1)) % 10 +
                (6 * (d0 + d1)) % 10;
     
    // no of residual terms
    int a = (k - 3) % 4;
     
    // sum of residual terms
    int x=0;
     
    switch(a)
    {
     
        // if no of residue term = 0
        case 0:
     
        x = 0;
        break;
     
        // if no of residue term = 1
        case 1:
     
        x = (2 * (d0 + d1)) % 10;
        break;
 
        // if no of residue term = 2
        case 2:
     
        x = (2 * (d0 + d1)) % 10 +
            (4 * (d0 + d1)) % 10;
        break;
     
        // if no of residue term = 3
        case 3:
     
        x = (2 * (d0 + d1)) % 10 +
            (4 * (d0 + d1)) % 10 +
            (8 * (d0 + d1)) % 10;
         
        break;
    }
     
    // sum of all digits
     int sum = d0 + d1 + (((k - 3) / 4) * s + x );
     
    // divisibility check
    if(sum % 3 == 0)
        return "YES";
    return "NO";
}
 
    //Code driven
     
    public static void main (String[] args) {
         
     int k, d0, d1;
     
    k = 13;
    d0 = 8;
    d1 = 1;
     
    System.out.println (check(k, d0, d1));
         
    k = 5;
    d0 = 3;
    d1 = 4;
         
        System.out.println (check(k, d0, d1));
         
    }
}

Python3

# Python3 code to check divisibility by 3
 
 
# Function to check the divisibility
def check(k, d0, d1):
 
    # Cycle
    s = ((2 * (d0 + d1)) % 10 +
        (4 * (d0 + d1)) % 10 +
        (8 * (d0 + d1)) % 10 +
        (6 * (d0 + d1)) % 10)
 
    # no of residual terms
    a = (k - 3) % 4
 
    # if no of residue term = 0
    if(a == 0):
        x = 0
 
    # if no of residue term = 1
    elif(a == 1):
        x = (2 * (d0 + d1)) % 10
 
    # if no of residue term = 2
    elif(a == 2):
        x = ((2 * (d0 + d1)) % 10 +
            (4 * (d0 + d1)) % 10)
 
    # if no of residue term = 3
    elif(a == 3):
        x = ((2 * (d0 + d1)) % 10 +
            (4 * (d0 + d1)) % 10 +
            (8 * (d0 + d1)) % 10)
 
    # sum of all digits
    sum = d0 + d1 + ((k - 3) // 4) * s + x
 
    # divisibility check
    if(sum % 3 == 0):
        return "YES"
    else:
        return "NO"
 
 
# Driver code
if __name__=='__main__':
    k = 13
    d0 = 8
    d1 = 1
 
    print(check(k, d0, d1))
 
    k = 5
    d0 = 3
    d1 = 4
 
    print(check(k, d0, d1))
 
# This code is contributed by
# Sanjit_Prasad

C#

// C# code to check divisibility by 3
using System;
 
class GFG
{
// Function to check the divisibility
static String check(int k, int d0, int d1)
{
 
    // Cycle
    int s = (2 * (d0 + d1)) % 10 +
            (4 * (d0 + d1)) % 10 +
            (8 * (d0 + d1)) % 10 +
            (6 * (d0 + d1)) % 10;
     
    // no of residual terms
    int a = (k - 3) % 4;
     
    // sum of residual terms
    int x = 0;
     
    switch(a)
    {
     
        // if no of residue term = 0
        case 0:
     
        x = 0;
        break;
     
        // if no of residue term = 1
        case 1:
     
        x = (2 * (d0 + d1)) % 10;
        break;
 
        // if no of residue term = 2
        case 2:
     
        x = (2 * (d0 + d1)) % 10 +
            (4 * (d0 + d1)) % 10;
        break;
     
        // if no of residue term = 3
        case 3:
     
        x = (2 * (d0 + d1)) % 10 +
            (4 * (d0 + d1)) % 10 +
            (8 * (d0 + d1)) % 10;
         
        break;
    }
     
    // sum of all digits
    int sum = d0 + d1 + (((k - 3) / 4) * s + x );
     
    // divisibility check
    if(sum % 3 == 0)
        return "YES";
    return "NO";
}
 
// Driver Code
static public void Main ()
{
     
    int k, d0, d1;
    k = 13;
    d0 = 8;
    d1 = 1;
     
    Console.WriteLine (check(k, d0, d1));
         
    k = 5;
    d0 = 3;
    d1 = 4;
         
    Console.WriteLine(check(k, d0, d1));
}
}
 
// This code is contributed by Sach_Code

PHP

<?php
// PHP code to check
// divisibility by 3
 
// Function to check
// the divisibility
function check($k, $d0,$d1)
{
 
    // Cycle
    $s = (2 * ($d0 + $d1)) % 10 +
         (4 * ($d0 + $d1)) % 10 +
         (8 * ($d0 + $d1)) % 10 +
         (6 * ($d0 + $d1)) % 10;
     
    // no of residual terms
    $a = ($k - 3) % 4;
     
    // sum of residual
    // terms
    $x;
     
    switch($a)
    {
     
        // if no of residue
        // term = 0
        case 0:
     
        $x = 0;
        break;
     
        // if no of residue
        // term = 1
        case 1:
     
        $x = (2 * ($d0 +
                   $d1)) % 10;
        break;
 
        // if no of residue
        // term = 2
        case 2:
     
        $x = (2 * ($d0 + $d1)) % 10 +
             (4 * ($d0 + $d1)) % 10;
        break;
     
        // if no of
        // residue term = 3
        case 3:
     
        $x = (2 * ($d0 + $d1)) % 10 +
             (4 * ($d0 + $d1)) % 10 +
             (8 * ($d0 + $d1)) % 10;
         
        break;
    }
     
    // sum of all digits
    $sum = $d0 + $d1 +
           (int)(($k - 3) /
              4) * $s + $x;
     
    // divisibility check
    if($sum % 3 == 0)
        return "YES";
    return "NO";
}
 
// Driver code
$k; $d0; $d1;
 
$k = 13;
$d0 = 8;
$d1 = 1;
 
echo check($k, $d0, $d1), "\n";
     
$k = 5;
$d0 = 3;
$d1 = 4;
     
echo check($k, $d0, $d1), "\n";
 
// This code is contributed by ajit
?>

Javascript

<script>
// Javascript code to check
// divisibility by 3
 
// Function to check
// the divisibility
function check(k, d0,d1)
{
 
    // Cycle
    let s = (2 * (d0 + d1)) % 10 +
        (4 * (d0 + d1)) % 10 +
        (8 * (d0 + d1)) % 10 +
        (6 * (d0 + d1)) % 10;
     
    // no of residual terms
    let a = (k - 3) % 4;
     
    // sum of residual
    // terms
    let x;
     
    switch(a)
    {
     
        // if no of residue
        // term = 0
        case 0:
     
        x = 0;
        break;
     
        // if no of residue
        // term = 1
        case 1:
     
        x = (2 * (d0 +
                d1)) % 10;
        break;
 
        // if no of residue
        // term = 2
        case 2:
     
        x = (2 * (d0 + d1)) % 10 +
            (4 * (d0 + d1)) % 10;
        break;
     
        // if no of
        // residue term = 3
        case 3:
     
        x = (2 * (d0 + d1)) % 10 +
            (4 * (d0 + d1)) % 10 +
            (8 * (d0 + d1)) % 10;
         
        break;
    }
     
    // sum of all digits
    let sum = d0 + d1 +
        parseInt((k - 3) /
            4) * s + x;
     
    // divisibility check
    if(sum % 3 == 0)
        return "YES";
    return "NO";
}
 
// Driver code
let k, d0, d1;
 
k = 13;
d0 = 8;
d1 = 1;
 
document.write(check(k, d0, d1) + "<br>");
     
k = 5;
d0 = 3;
d1 = 4;
     
document.write(check(k, d0, d1) + "<br>");
 
// This code is contributed by gfgking.
</script>
Producción: 

YES
NO

 

Complejidad de tiempo : O(1)
 

Publicación traducida automáticamente

Artículo escrito por agnivakolay 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 *