Check divisibility in a binary stream
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
/* 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" ; } } |
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 () # convert incoming bit to integer incomingBit = int (incomingBit) # Update value of num formed so far 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)) { // 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. 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
// JavaScript function checkDivisibility2(n) { let num = 0; console.log( "Press any key other than 0 and 1 to terminate" ); while ( true ) { let incomingBit = prompt(); // convert incoming bit to integer incomingBit = parseInt(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) { 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
// 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 |
Javascript
// JavaScript 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. 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) => { // 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. const incomingBit = parseInt(input); // Update remainder if (incomingBit === 1) remainder = (remainder * 2 + 1) % n; else if (incomingBit === 0) remainder = (remainder * 2) % n; else { readline.close(); return ; } // If remainder is 0. if (remainder % n === 0) console.log( "yes" ); else console.log( "no" ); }); } // Driver code CheckDivisibility(3); // This code is contributed by shivamsharma215 |
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