Considere un número N muy largo de K dígitos con dígitos d 0 , d 1 , …, d K-1 (en notación decimal; d 0 es el dígito más significativo y d K-1 el dígito menos significativo). Este número es tan grande que no se puede dar ni escribir explícitamente; en cambio, solo se dan sus dígitos iniciales y una forma de construir el resto del número.
Específicamente, se le da d 0 y d 1 ; para cada i ≥ 2, d i es la suma de todos los dígitos anteriores (más significativos), módulo 10, más formalmente:
determine si N es un múltiplo de 3.
Restricciones:
2 ≤K ≤10 12
1 ≤d 0 ≤9
0 ≤d 1 ≤9
Ejemplos:
Input : K = 13, d0 = 8, d1 = 1 Output : YES
Explicación: el número entero N es 8198624862486 , que es divisible por 3,
por lo que la respuesta es SÍ.
Input : K = 5, d0 = 3, d1 = 4 Output : NO
Explicación: el número entero N es 34748 , que no es divisible por 3,
por lo que la respuesta es NO.
Método 1 (Fuerza bruta)
Podemos aplicar el método de fuerza bruta para calcular el número entero N usando la condición dada para construir el número iterativamente (suma de los números anteriores módulo 10) y verificar si el número es divisible por 3 o no. Pero dado que el número de dígitos (K) puede ser tan grande como 10 12 , no podemos almacenarlo como un número entero ya que será mucho mayor que el rango máximo de ‘long long int’. Por lo tanto, a continuación se muestra un método eficiente para determinar si N es un múltiplo de 3.
Método 2 (eficiente)
La idea clave detrás de la solución es el hecho de que los dígitos comienzan a repetirse después de un tiempo en un ciclo de longitud 4. Primero, encontraremos la suma de todos los dígitos y luego determinaremos si es divisible por 3 o NO.
Sabemos d 0 y d 1 .
re 2 = ( re 0 + re 1 ) % 10
re 3 = ( re 2 + re 1 + re 0 ) % 10 = (( re 0 + re 1 ) % 10 + re 0 + re 1 ) % 10 = 2 * ( re 0 + re 1 ) % 10
De manera similar,
re 4 = ( re 3 + re 2 + re 1 + re 0 ) % 10 = 4 * ( re 0 + re 1) % 10
re 5 = ( re 4 + re 3 + re 2 + re 1 + re 0 ) % 10 = 8 * ( re 0 + re 1 ) % 10
re 6 = ( re 5 + … + re 1 + re 0 ) % 10 = 16 * (re 0 + re 3 ) % 10 = 6 * ( re 0 + re 1 ) % 10
re 7 = ( re 6 + … + re 1 + re 0 ) % 10 = 12 * ( re 0 + re 1 ) % 10 =2 * ( día 0 + día 1 ) % 10
Si seguimos encontrando en d i , veremos que la resultante simplemente gira alrededor de los mismos valores (2, 4, 8, 6).
Aquí la duración del ciclo es 4 y d 2 no está presente en el ciclo. Por lo tanto, después de d 2 , el ciclo comienza a formarse con una longitud de 4 a partir de cualquier valor en (2, 4, 8, 6) pero en el mismo orden dando una suma de S = 2 + 4 + 8 + 6 = 20 para cuatro dígitos consecutivos . Por lo tanto, la suma total de dígitos para el número entero es = d 0 + d 1 + d 2 + S*(k – 3)/4 + x, donde los primeros tres términos estarán cubiertos por d 0 , d 1 , d 2
y después de eso, los grupos de 4 estarán cubiertos por S. Pero dado que (k – 3) puede no ser un múltiplo de 4, quedarán algunos dígitos restantes que están cubiertos por x, que se pueden calcular ejecutando un bucle como ese número de términos será menor que 4.
Por ejemplo , cuando K = 13,
suma de dígitos = d 0 + d 1 + d 2 + S * (13 – 3) / 4 + x = d 0 + d 1 + d 2 + S * 2 + x,
donde primero S tendrá d 3 , d 4 , d 5 , d 6 y la segunda S tendrá d 7 , d 8 , d 9 , d 10 y
x = d 11 + d 12
- re 11 = 2 * ( re 0 + re 1 ) % 10
- re 12 = 4 * ( re 0 + re 1 ) % 10
A continuación se muestra la implementación de la idea anterior:
C++
// CPP Program to determine if
// number N of given form is
// divisible by 3 or not
#include <bits/stdc++.h>
using namespace std;
// function returns true if number N is
// divisible by 3 otherwise false,
// dig0 - most significant digit
// dig1 - 2nd most significant digit
// K - number of digits
bool multipleOfThree(int K, int dig0, int dig1)
{
// sum of digits
long long int sum = 0;
// store the sum of first two digits
// modulo 10 in a temporary variable
int temp = (dig0 + dig1) % 10;
sum = dig0 + dig1;
// if the number N is a two digit number
if (K == 2) {
if (sum % 3 == 0)
return true;
else
return false;
}
// add temp to sum to get the sum
// of first three digits which are
// not a part of cycle
sum += temp;
// get the number of groups in cycle
long long int numberofGroups = (K - 3) / 4;
// get the remaining number of digits
int remNumberofDigits = (K - 3) % 4;
// if temp = 5 or temp = 0 then sum of each group will
// be 0
if (temp == 5 || temp == 0)
sum += (numberofGroups * 0);
else
// add sum of 20 for each group (2, 4, 8, 6)
sum += (numberofGroups * 20);
// find the remaining sum of remaining digits
for (int i = 0; i < remNumberofDigits; i++) {
temp = (2 * temp) % 10;
sum += temp;
}
// check if it is divisible by 3 or not
if (sum % 3 == 0)
return true;
else
return false;
}
// Driver Code
int main()
{
int K = 5, dig0 = 3, dig1 = 4;
if (multipleOfThree(K, dig0, dig1))
cout << "YES" << endl;
else
cout << "NO" << endl;
K = 10;
dig0 = 3;
dig1 = 2;
if (multipleOfThree(K, dig0, dig1))
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
Java
// Java Program to determine if
// number N of given form is
// divisible by 3 or not
import java.io.*;
public class GFG {
// function returns true if number N is
// divisible by 3 otherwise false,
// dig0 - most significant digit
// dig1 - 2nd most significant digit
// K - number of digits
static boolean multipleOfThree(int K, int dig0,
int dig1)
{
// sum of digits
long sum = 0;
// store the sum of first two digits
// modulo 10 in a temporary variable
int temp = (dig0 + dig1) % 10;
sum = dig0 + dig1;
// if the number N is a two digit number
if (K == 2) {
if (sum % 3 == 0)
return true;
else
return false;
}
// add temp to sum to get the sum
// of first three digits which are
// not a part of cycle
sum += temp;
// get the number of groups in cycle
long numberofGroups = (K - 3) / 4;
// get the remaining number of digits
int remNumberofDigits = (K - 3) % 4;
// add sum of 20 for each group (2, 4, 8, 6)
sum += (numberofGroups * 20);
// find the remaining sum of
// remaining digits
for (int i = 0; i < remNumberofDigits; i++) {
temp = (2 * temp) % 10;
sum += temp;
}
// check if it is divisible by 3 or not
if (sum % 3 == 0)
return true;
else
return false;
}
// Driver Code
static public void main(String[] args)
{
int K = 5, dig0 = 3, dig1 = 4;
if (multipleOfThree(K, dig0, dig1))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by vt_m.
Python 3
# Python 3 Program to determine if
# number N of given form is
# divisible by 3 or not
# function returns true if number N
# is divisible by 3 otherwise false,
# dig0 - most significant digit
# dig1 - 2nd most significant digit
# K - number of digits
def multipleOfThree(K, dig0, dig1):
# sum of digits
sum = 0
# store the sum of first two digits
# modulo 10 in a temporary variable
temp = (dig0 + dig1) % 10
sum = dig0 + dig1
# if the number N is a
# two digit number
if (K == 2):
if (sum % 3 == 0):
return True
else:
return False
# add temp to sum to get the sum
# of first three digits which are
# not a part of cycle
sum += temp
# get the number of groups in cycle
numberofGroups = (K - 3) // 4
# get the remaining number of digits
remNumberofDigits = (K - 3) % 4
# add sum of 20 for each
# group (2, 4, 8, 6)
sum += (numberofGroups * 20)
# find the remaining sum of
# remaining digits
for i in range(remNumberofDigits):
temp = (2 * temp) % 10
sum += temp
# check if it is divisible
# by 3 or not
if (sum % 3 == 0):
return True
else:
return False
# Driver Code
if __name__ == "__main__":
K = 5
dig0 = 3
dig1 = 4
if (multipleOfThree(K, dig0, dig1)):
print("Yes")
else:
print("No")
# This code is contributed by ChitraNayal
C#
// C# Program to determine if
// number N of given form is
// divisible by 3 or not
using System;
class GFG {
// function returns true if number N is
// divisible by 3 otherwise false,
// dig0 - most significant digit
// dig1 - 2nd most significant digit
// K - number of digits
static bool multipleOfThree(int K, int dig0, int dig1)
{
// sum of digits
long sum = 0;
// store the sum of first two digits
// modulo 10 in a temporary variable
int temp = (dig0 + dig1) % 10;
sum = dig0 + dig1;
// if the number N is
// a two digit number
if (K == 2) {
if (sum % 3 == 0)
return true;
else
return false;
}
// add temp to sum to get the sum
// of first three digits which are
// not a part of cycle
sum += temp;
// get the number of groups in cycle
long numberofGroups = (K - 3) / 4;
// get the remaining number of digits
int remNumberofDigits = (K - 3) % 4;
// add sum of 20 for each group (2, 4, 8, 6)
sum += (numberofGroups * 20);
// find the remaining sum of
// remaining digits
for (int i = 0; i < remNumberofDigits; i++) {
temp = (2 * temp) % 10;
sum += temp;
}
// check if it is divisible by 3 or not
if (sum % 3 == 0)
return true;
else
return false;
}
// Driver Code
static public void Main(String[] args)
{
int K = 5, dig0 = 3, dig1 = 4;
if (multipleOfThree(K, dig0, dig1))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Program to determine if number N
// of given form is divisible by 3 or not
// function returns true if number N
// is divisible by 3 otherwise false,
// dig0 - most significant digit
// dig1 - 2nd most significant digit
// K - number of digits
function multipleOfThree($K, $dig0, $dig1)
{
// sum of digits
$sum = 0;
// store the sum of first two digits
// modulo 10 in a temporary variable
$temp = ($dig0 + $dig1) % 10;
$sum = $dig0 + $dig1;
// if the number N is a
// two digit number
if ($K == 2)
if ($sum % 3 == 0)
return true;
else
return false;
// add temp to sum to get the sum
// of first three digits which are
// not a part of cycle
$sum += $temp;
// get the number of groups in cycle
$numberofGroups = (int)(($K - 3) / 4);
// get the remaining number of digits
$remNumberofDigits = ($K - 3) % 4;
// add sum of 20 for each
// group (2, 4, 8, 6)
$sum += ($numberofGroups * 20);
// find the remaining sum of
// remaining digits
for ($i = 0; $i < $remNumberofDigits; $i++)
{
$temp = (2 * $temp) % 10;
$sum += $temp;
}
// check if it is divisible
// by 3 or not
if ($sum % 3 == 0)
return true;
else
return false;
}
// Driver Code
$K = 5;
$dig0 = 3;
$dig1 = 4;
if (multipleOfThree($K, $dig0, $dig1))
print("Yes");
else
print("No");
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript Program to determine if
// number N of given form is
// divisible by 3 or not
// function returns true if number N is
// divisible by 3 otherwise false,
// dig0 - most significant digit
// dig1 - 2nd most significant digit
// K - number of digits
function multipleOfThree(K, dig0, dig1)
{
// sum of digits
let sum = 0;
// store the sum of first two digits
// modulo 10 in a temporary variable
let temp = (dig0 + dig1) % 10;
sum = dig0 + dig1;
// if the number N is a two digit number
if (K == 2) {
if (sum % 3 == 0)
return true;
else
return false;
}
// add temp to sum to get the sum
// of first three digits which are
// not a part of cycle
sum += temp;
// get the number of groups in cycle
let numberofGroups = parseInt((K - 3) / 4);
// get the remaining number of digits
let remNumberofDigits = (K - 3) % 4;
// if temp = 5 or temp = 0 then sum of each group will
// be 0
if (temp == 5 || temp == 0)
sum += (numberofGroups * 0);
else
// add sum of 20 for each group (2, 4, 8, 6)
sum += (numberofGroups * 20);
// find the remaining sum of remaining digits
for (let i = 0; i < remNumberofDigits; i++) {
temp = (2 * temp) % 10;
sum += temp;
}
// check if it is divisible by 3 or not
if (sum % 3 == 0)
return true;
else
return false;
}
// Driver Code
let K = 5, dig0 = 3, dig1 = 4;
if (multipleOfThree(K, dig0, dig1))
document.write("YES<br>");
else
document.write("NO<br>");
K = 10;
dig0 = 3;
dig1 = 2;
if (multipleOfThree(K, dig0, dig1))
document.write("YES<br>");
else
document.write("NO<br>");
</script>
NO NO
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA