Se acerca un flujo de números binarios, la tarea es decir que el número formado hasta ahora es divisible por un número dado n. En un momento dado, obtendrás 0 o 1 y dirás si el número formado con estos bits es divisible por n o no. Generalmente, las empresas de comercio electrónico hacen este tipo de preguntas. Me lo preguntaron en la entrevista de Microsoft. En realidad, esa pregunta era un poco simple, el entrevistador fijó la n en 3. Método 1 (Simple pero causa desbordamiento): Continúe calculando el número formado y solo verifique la divisibilidad entre n.
C
/* Simple implementation of the logic,
without error handling compiled with
Microsoft visual studio 2015 */
void CheckDivisibility2(int n)
{
int num = 0;
std::cout << "press any key other than"
" 0 and 1 to terminate \n";
while (true)
{
int incomingBit;
// read next incoming bit via standard
// input. 0, 00, 000.. are same as int 0
// ans 1, 01, 001, 00..001 is same as 1.
std::cin >> incomingBit;
// Update value of num formed so far
if (incomingBit == 1)
num = (num * 2 + 1);
else if (incomingBit == 0)
num = (num * 2);
else
break;
if (num % n == 0)
std::cout << "yes \n";
else
std::cout << "no \n";
}
}
Problema en esta solución: ¿Qué pasa con el desbordamiento? Dado que 0 y 1 seguirán apareciendo y el número formado saldrá del rango de entero. Método 2 (no causa desbordamiento): en esta solución, solo mantenemos el resto si el resto es 0, el número formado es divisible por n, de lo contrario no. Esta es la misma técnica que se usa en Automata.para recordar el estado. Aquí también estamos recordando el estado de divisibilidad del número de entrada. Para implementar esta técnica, necesitamos observar cómo cambia el valor de un número binario, cuando se agrega 0 o 1. Tomemos un ejemplo. Supongamos que tiene el número binario 1. Si se agrega 0, se convertirá en 10 (2 en decimal), lo que significa 2 veces el valor anterior. Si se le añade 1 se convertirá en 11 (3 en decimal), 2 veces el valor anterior +1. ¿Cómo ayuda a obtener el resto?Cualquier número (n) se puede escribir en la forma m = an + r donde a, n y r son números enteros y r es el resto. Entonces, cuando m se multiplica por cualquier número, el resto. Supongamos que m se multiplica por x, por lo que m será mx = xan + xr. entonces (mx)%n = (xan)%n + (xr)%n = 0 + (xr)%n = (xr)%n; Solo necesitamos hacer el cálculo anterior (cálculo del valor del número cuando se agrega 0 o 1) solo sobre el resto.
When a binary number is appended by 0 (means multiplied by 2), the new remainder can be calculated based on current remainder only. r = 2*r % n; And when a binary number is appended by 1. r = (2*r + 1) % n;
CPP
// C++ program to check divisibility in a stream
#include <iostream>
using namespace std;
/* A very simple implementation of the logic,
without error handling. just to demonstrate
the above theory. This simple version not
restricting user from typing 000, 00 , 000.. ,
because this all will be same as 0 for integer
same is true for 1, 01, 001, 000...001 is same
as 1, so ignore this type of error handling
while reading just see the main logic is correct. */
void CheckDivisibility(int n)
{
int remainder = 0;
std::cout << "press any key other than 0"
" and 1 to terminate \n";
while (true)
{
// Read next incoming bit via standard
// input. 0, 00, 000.. are same as int 0
// ans 1, 01, 001, 00..001 is same as 1.
int incomingBit;
cin >> incomingBit;
// Update remainder
if (incomingBit == 1)
remainder = (remainder * 2 + 1) % n;
else if (incomingBit == 0)
remainder = (remainder * 2) % n;
else
break;
// If remainder is 0.
if (remainder % n == 0)
cout << "yes \n";
else
cout << "no \n";
}
}
// Driver code
int main()
{
CheckDivisibility(3);
return 0;
}
Java
// Java program to check divisibility in a stream
import java.util.Scanner;
/* A very simple implementation of the logic,
without error handling. just to demonstrate
the above theory. This simple version not
restricting user from typing 000, 00 , 000.. ,
because this all will be same as 0 for integer
same is true for 1, 01, 001, 000...001 is same
as 1, so ignore this type of error handling
while reading just see the main logic is correct. */
class GFG {
static void CheckDivisibility(int n)
{
Scanner console = new Scanner(System.in);
int remainder = 0;
System.out.print("press any key other than 0 and 1 to terminate \n");
while (true)
{
// Read next incoming bit via standard
// input. 0, 00, 000.. are same as int 0
// ans 1, 01, 001, 00..001 is same as 1.
int incomingBit = console.nextInt();
// Update remainder
if (incomingBit == 1)
remainder = (remainder * 2 + 1) % n;
else if (incomingBit == 0)
remainder = (remainder * 2) % n;
else
break;
// If remainder is 0.
if (remainder % n == 0)
System.out.print("yes \n");
else
System.out.print("no \n");
}
}
//Driver code
public static void main(String[] args) {
CheckDivisibility(3);
}
}
//This code is contributed by phasing17
Python3
#Python3 program to check divisibility in a stream
''' A very simple implementation of the logic,
without error handling. just to demonstrate
the above theory. This simple version not
restricting user from typing 000, 00 , 000.. ,
because this all will be same as 0 for integer
same is true for 1, 01, 001, 000...001 is same
as 1, so ignore this type of error handling
while reading just see the main logic is correct. '''
def CheckDivisibility(n):
remainder = 0
print("press any key other than 0"
" and 1 to terminate")
while (True):
# Read next incoming bit via standard
# input. 0, 00, 000.. are same as int 0
# ans 1, 01, 001, 00..001 is same as 1.
incomingBit = int(input())
# Update remainder
if (incomingBit == 1):
remainder = (remainder * 2 + 1) % n
elif (incomingBit == 0):
remainder = (remainder * 2) % n
else:
break
# If remainder is 0.
if (remainder % n == 0):
print("yes")
else:
print("no")
# Driver code
CheckDivisibility(3)
#this code is contributed by phasing17
C#
// C# program to check divisibility in a stream
using System;
/* A very simple implementation of the logic,
without error handling. just to demonstrate
the above theory. This simple version not
restricting user from typing 000, 00 , 000.. ,
because this all will be same as 0 for integer
same is true for 1, 01, 001, 000...001 is same
as 1, so ignore this type of error handling
while reading just see the main logic is correct. */
public class GFG
{
static void CheckDivisibility(int n)
{
int remainder = 0;
Console.Write("press any key other than 0 and 1 to terminate \n");
while (true)
{
// Read next incoming bit via standard
// input. 0, 00, 000.. are same as int 0
// ans 1, 01, 001, 00..001 is same as 1.
int incomingBit = Convert.ToInt32(Console.ReadLine());
// Update remainder
if (incomingBit == 1)
remainder = (remainder * 2 + 1) % n;
else if (incomingBit == 0)
remainder = (remainder * 2) % n;
else
break;
// If remainder is 0.
if (remainder % n == 0)
Console.Write("yes \n");
else
Console.Write("no \n");
}
}
//Driver Code
public static void Main(string[] args)
{
//Function call
CheckDivisibility(3);
}
}
// This code is contributed by phasing17
Aporte:
1 0 1 0 1 -1
Producción:
Press any key other than 0 and 1 to terminate no no no no yes
Artículos relacionados: división basada en DFA Comprobar si una secuencia es múltiplo de 3 Puneet contribuye con este artículo . 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA