Check divisibility in a binary stream
Last Updated :
23 Nov, 2023
Stream of binary number is coming, the task is to tell the number formed so far is divisible by a given number n. At any given time, you will get 0 or 1 and tell whether the number formed with these bits is divisible by n or not. Generally, e-commerce companies ask this type of questions. It was asked me in Microsoft interview. Actually that question was a bit simple, interviewer fixed the n to 3.
Method 1 (Simple but causes overflow):Keep on calculating the number formed and just check divisibility by n.
C++
#include <iostream>
using namespace std;
int main() {
int n = 0;
int num = 0;
cout << "Enter a value for n: ";
cin >> n;
cout << "Press any key other than 0 and 1 to terminate" << endl;
while (true) {
int incomingBit;
cin >> incomingBit;
if (incomingBit == 1) {
num = (num * 2 + 1);
} else if (incomingBit == 0) {
num = (num * 2);
} else {
break;
}
if (num % n == 0) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
}
return 0;
}
|
C
void CheckDivisibility2(int n)
{
int num = 0;
std::cout << "press any key other than"
" 0 and 1 to terminate \n";
while (true)
{
int incomingBit;
std::cin >> incomingBit;
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";
}
}
|
Java
import java.util.Scanner;
public class CheckDivisibility2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = 0;
int num = 0;
System.out.println("Enter a value for n:");
n = scanner.nextInt();
System.out.println("Press any key other than 0 and 1 to terminate");
while (true) {
int incomingBit = scanner.nextInt();
if (incomingBit == 1) {
num = (num * 2 + 1);
} else if (incomingBit == 0) {
num = (num * 2);
} else {
break;
}
if (num % n == 0) {
System.out.println("yes");
} else {
System.out.println("no");
}
}
scanner.close();
}
}
|
Python3
def CheckDivisibility2(n):
num = 0
print("press any key other than 0 and 1 to terminate")
while True:
incomingBit = input()
incomingBit = int(incomingBit)
if incomingBit == 1:
num = (num * 2 + 1)
elif incomingBit == 0:
num = (num * 2)
else:
break
if num % n == 0:
print("yes")
else:
print("no")
|
C#
static void CheckDivisibility2(int n)
{
int num = 0;
Console.WriteLine("press any key other than" +
" 0 and 1 to terminate");
while (true)
{
int incomingBit;
if (Int32.TryParse(Console.ReadLine(), out incomingBit))
{
if (incomingBit == 1)
num = (num * 2 + 1);
else if (incomingBit == 0)
num = (num * 2);
else
break;
if (num % n == 0)
Console.WriteLine("yes");
else
Console.WriteLine("no");
}
else
{
Console.WriteLine("Invalid input. Program terminated.");
break;
}
}
}
|
Javascript
function checkDivisibility2(n) {
let num = 0;
console.log("Press any key other than 0 and 1 to terminate");
while (true) {
let incomingBit = prompt();
incomingBit = parseInt(incomingBit);
if (incomingBit === 1) {
num = num * 2 + 1;
} else if (incomingBit === 0) {
num = num * 2;
} else {
break;
}
if (num % n === 0) {
console.log("yes");
} else {
console.log("no");
}
}
}
|
Problem in this solution: What about the overflow. Since 0 and 1 will keep on coming and the number formed will go out of range of integer.
Method 2 (Doesn’t cause overflow) :In this solution, we just maintain the remainder if remainder is 0, the formed number is divisible by n otherwise not. This is the same technique that is used in Automata to remember the state. Here also we are remembering the state of divisibility of input number. In order to implement this technique, we need to observe how the value of a binary number changes, when it is appended by 0 or 1. Let’s take an example. Suppose you have binary number 1. If it is appended by 0 it will become 10 (2 in decimal) means 2 times of the previous value. If it is appended by 1 it will become 11(3 in decimal), 2 times of previous value +1.
How does it help in getting the remainder?
Any number (n) can be written in the form m = an + r where a, n and r are integers and r is the remainder. So when m is multiplied by any number so the remainder. Suppose m is multiplied by x so m will be mx = xan + xr. so (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;
CPP
#include <iostream>
using namespace std;
void CheckDivisibility(int n)
{
int remainder = 0;
std::cout << "press any key other than 0"
" and 1 to terminate \n";
while (true)
{
int incomingBit;
cin >> incomingBit;
if (incomingBit == 1)
remainder = (remainder * 2 + 1) % n;
else if (incomingBit == 0)
remainder = (remainder * 2) % n;
else
break;
if (remainder % n == 0)
cout << "yes \n";
else
cout << "no \n";
}
}
int main()
{
CheckDivisibility(3);
return 0;
}
|
Java
import java.util.Scanner;
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)
{
int incomingBit = console.nextInt();
if (incomingBit == 1)
remainder = (remainder * 2 + 1) % n;
else if (incomingBit == 0)
remainder = (remainder * 2) % n;
else
break;
if (remainder % n == 0)
System.out.print("yes \n");
else
System.out.print("no \n");
}
}
public static void main(String[] args) {
CheckDivisibility(3);
}
}
|
Python3
def CheckDivisibility(n):
remainder = 0
print("press any key other than 0"
" and 1 to terminate")
while (True):
incomingBit = int(input())
if (incomingBit == 1):
remainder = (remainder * 2 + 1) % n
elif (incomingBit == 0):
remainder = (remainder * 2) % n
else:
break
if (remainder % n == 0):
print("yes")
else:
print("no")
CheckDivisibility(3)
|
C#
using System;
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)
{
int incomingBit = Convert.ToInt32(Console.ReadLine());
if (incomingBit == 1)
remainder = (remainder * 2 + 1) % n;
else if (incomingBit == 0)
remainder = (remainder * 2) % n;
else
break;
if (remainder % n == 0)
Console.Write("yes \n");
else
Console.Write("no \n");
}
}
public static void Main(string[] args)
{
CheckDivisibility(3);
}
}
|
Javascript
function CheckDivisibility(n) {
const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
let remainder = 0;
console.log("press any key other than 0 and 1 to terminate");
readline.on('line', (input) => {
const incomingBit = parseInt(input);
if (incomingBit === 1)
remainder = (remainder * 2 + 1) % n;
else if (incomingBit === 0)
remainder = (remainder * 2) % n;
else {
readline.close();
return;
}
if (remainder % n === 0)
console.log("yes");
else
console.log("no");
});
}
CheckDivisibility(3);
|
Input:
1
0
1
0
1
-1
Output:
Press any key other than 0 and 1 to terminate
no
no
no
no
yes
Time Complexity: O(N), where N is the number of inputs
Auxiliary Space: O(1)
Related Articles: DFA based division Check if a stream is Multiple of 3
Similar Reads
Check divisibility of binary string by 2^k
Given a binary string and a number k, the task is to check whether the binary string is evenly divisible by 2k or not. Examples : Input : 11000 k = 2Output : YesExplanation :(11000)2 = (24)1024 is evenly divisible by 2k i.e. 4. Input : 10101 k = 3Output : NoExplanation : (10101)2 = (21)1021 is not e
10 min read
Check divisibility by 7
Given a number n, the task is to check if it is divisible by 7 or not.Note: You are not allowed to use the modulo operator, floating point arithmetic is also not allowed. Examples: Input: n = 371Output: TrueExplanation: The number 371: 37 - (2×1) = 37 - 2 = 35; 3 - (2 × 5) = 3 - 10 = -7; thus, since
6 min read
Check if a large number is divisibility by 15
Given a very large number. Check its divisibility by 15. Examples: Input: "31"Output: NoInput : num = "156457463274623847239840239 402394085458848462385346236 482374823647643742374523747 264723762374620"Output: YesGiven number is divisible by 15A number is divisible by 15 if it is divisible by 5 (if
5 min read
Check if a large number is divisible by 20
Given a number, the task is to check if number is divisible by 20. The input number may be large and it may not be possible to store long long int and it may be very large number then we use the string.Examples: Input : 7575680 Output : Yes Input : 987985865687690 Output : No A number is divisible b
6 min read
Check if a larger number divisible by 36
Given a number, check whether a given number is divisible by 36 or not. The number may be very large and may not fit in any numeric(int, long int, float, etc.) data type.Examples: Input : 72Output : YesInput : 244Output : NoInput : 11322134Output : NoInput : 92567812197966231384Output : YesRecommend
12 min read
Check if a Binary Tree is univalued or not
Given a binary tree, the task is to check if the binary tree is univalued or not. If found to be true, then print "YES". Otherwise, print "NO". A binary tree is univalued if every node in the tree has the same value. Example: Input: 1 / \ 1 1 / \ \ 1 1 1 Output: YES Explanation: The value of all the
14 min read
Check if a number is divisible by 47 or not
Given a number N, the task is to check whether the number is divisible by 47 or not. Examples: Input: N = 1645 Output: yes Explanation: 47 * 35 = 1645Input: N = 4606 Output: yes Explanation: 47 * 98 = 4606 Approach: The divisibility test of 47 is: Extract the last digit.Subtract 14 * last digit from
6 min read
Check if a number is divisible by 31 or not
Given a number N, the task is to check whether the number is divisible by 31 or not. Examples: Input: N = 1922 Output: Yes Explanation: 31 * 62 = 1922Input: N = 2722400 Output: No Approach: The divisibility test of 31 is: Extract the last digit.Subtract 3 * last digit from the remaining number obtai
5 min read
Check if a large number is divisible by 8 or not
Given a number, the task is to check if a number is divisible by 8 or not. The input number may be large and it may not be possible to store even if we use long long int.Examples: Input : n = 1128Output : YesInput : n = 1124Output : NoInput : n = 363588395960667043875487Output : NoSince input number
13 min read
Check if a large number is divisible by 4 or not
Given a number, the task is to check if a number is divisible by 4 or not. The input number may be large and it may not be possible to store even if we use long long int. Examples: Input : n = 1124Output : YesInput : n = 1234567589333862Output : NoInput : n = 363588395960667043875487Output : No Usin
12 min read