Проверить делимость в двоичном потоке

Опубликовано: 20 Января, 2022

Идет поток двоичного числа, задача - сказать, что образовавшееся число делится на заданное число n.
В любой момент вы получите 0 или 1 и узнаете, делится ли число, образованное этими битами, на n или нет.

Обычно такие вопросы задают компании электронной коммерции. Об этом меня спрашивали в интервью Microsoft. На самом деле этот вопрос был немного простым, интервьюер установил n равным 3.

Method 1 (Simple but causes overflow):

Keep on calculating the number formed and just check divisibility by n.
/* 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 ";
    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 ";
        else
            std::cout << "no ";
    }
}

Проблема в этом решении: А как насчет переполнения. Поскольку 0 и 1 будут продолжать поступать, а образованное число выйдет за пределы целого диапазона.


Способ 2 (не вызывает переполнения):

В этом решении мы просто сохраняем остаток, если остаток равен 0, в противном случае сформированное число делится на n. Это тот же метод, который используется в автоматах для запоминания состояния. Здесь мы также запоминаем состояние делимости входного числа.

Чтобы реализовать эту технику, нам нужно наблюдать, как изменяется значение двоичного числа, когда к нему добавляются 0 или 1.

Возьмем пример. Предположим, у вас есть двоичное число 1.
Если к нему добавлен 0, он станет 10 (2 в десятичной системе), что означает, что в 2 раза больше предыдущего значения.
Если к нему добавить 1, оно станет 11 (3 в десятичной системе), что в 2 раза превышает предыдущее значение +1.

Как это помогает получить остаток?
Любое число (n) можно записать в виде m = an + r, где a, n и r - целые числа, а r - остаток. Итак, когда m умножается на любое число, получается остаток. Предположим, что m умножено на x, поэтому m будет mx = xan + xr. поэтому (mx)% n = (xan)% n + (xr)% n = 0 + (xr)% n = (xr)% n;

We need to just do the above calculation (calculation of value of number when it is appended by 0 or 1 ) only over remainder.

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;
// 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 ";
    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 ";
        else
            cout << "no ";
    }
}
  
// Driver code
int main()
{
    CheckDivisibility(3);
    return 0;
}

Вход:

1
0
1
0
1
-1

Выход:

Нажмите любую клавишу, кроме 0 и 1, чтобы завершить 
нет 
нет 
нет 
нет 
да

Статьи по Теме:
Подразделение на основе DFA
Убедитесь, что поток кратен 3

Эта статья предоставлена Puneet . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ