Microsoft Interview Question Software Engineer / Developers
Team: bing
Country: India
Interview Type: In-Person
I think this is right answer.
while(1)
{
if (input) k = k*2 +1;
else k = k*2;
k = k%3;
if (k == 0 ) //current can be divisible by 3.
}
Similar solution: added by hitman in another thread..
bool divisibleBy3(bool next_bit)
{
static int remainder = 0;
remainder = ((remainder * 2) + (next_bit ? 1 : 0)) % 3;
return (remainder == 0);
}
keep track of the number of set bits (1's) in the odd positions, and the number of set bits in the even positions.
if the absolute difference of both values is divisible by 3, then the number is divisible by 3.
here is the proof.
Our goal is to show that every 2^k number could be represented as 3*p +/- 1 (plus or minus) form, and also if 2^k = 3p + 1 then 2^(k+1) = 3*q - 1 and vice versa.
first part is very easy. every integer can be represented in one of the following 3 forms: 3*p - 1 (or the same is 3*q + 2), 3*p or 3*p + 1. Note that 2^k <> 3*p as 2^k does not contain 3 multiplier, so 2^k = 3*p - 1 or 2^k = 3*p + 1.
now assume 2^k = 3*p - 1. Then 2^(k+1) = 2 * (3*p - 1) = 6*p - 2 = 3 * (2*p) - 2 = 3 * q + 1. And the same we can do for 2^k = 3*p+1.
Didn't really understand the proof, but this is very similar to divisibility by 11 for a base 10 number as 3 is 11 in base 2.
It would be a fair objection to say, however, that storing the number of occurrences of anything requires O(logN) space, since the number counting the occurrences will have that many digits. It's possible to solve this in O(1) space by simply keeping a state machine with 6 states.
Have a function f: current remainder (0, 1, or 2) x incoming digit (0 or 1) -> new remainder (0, 1, or 2)
It isn't hard to determine what this function should be simply by modular arithmetic
0 remainder x 0 incoming digit -> 0
1 remainder x 0 incoming digit -> 2
...
How these numbers are derived is described in the other well-rated response.
At start keep teh count of number of zero till you encounter first '1' bit. At this time calculate the decimal number.
Now keep updating it using the left shift concept.
Left shift with 0 doubles the number.
Left shift with 1 2*number+1
Once you have the number it is easy to check that it is divisible by three or nor.
let we already n bits have gone and currently we have n+ 1 th bit.
for n bit we know the flag then calculate the flag for n+1 th bit as:
—-----------------------------------
n+1 th bit. last flag. new flag
0. 0. 0
0. 1. 2
0. 2. 1
1. 0. 1
1. 1. 0
1. 2. 2
proof: let last number with n bits: (3k+flag)
so next number will be 2(3k+last flag)+(n+1th) bit.
whenever flag is zero it will be divisible by 3.
Instead of calculating the number everytime, since the stream is infinite, this can be done as follows.
#include<stdio.h>
main()
{
char ch='\0';
unsigned short int remainder=0, n=0;
while(1)
{
scanf("%c",&ch);
n++;
if(ch=='1')
{
if((n-1)%2==0)
remainder = remainder + 1;
else
remainder = remainder + 2;
}
else if(ch=='0')
{
remainder = remainder + 0;
}
else
break;
if(n==2)
n=0;
if(remainder%3==0)
{
printf("Yes\n");
remainder = 0;
}
else
printf("No\n");
}
}
I think this problem can be solved using the fact that if sum of digits of a number is divisible by 3 than that no is also divisible by 3. now if that sum is divisible by 3 than sum of its digits is also divisible by 3. so if we keep adding digits of this sum until we get a single digit(<9), than this digit must be divisible by 3.
now here problem is that, we have to play with bits. but than can also be dealt in same way as we can deal it with decimal nos. here is my solution(i tested this with different inputs and it is working fine)
int main()
{
int sum=0;
while(1)
{
c = getNextBit(); // returns next bit as char from stream
if(c!='0' && c!='1')
break;
if(c=='0')
sum = sum*2;
if(c=='1')
sum = (sum*2)+1;
if(sum>9)
sum = addDigits(sum);
if(sum%3==0)
printf("%c:sum %d is divisible by 3\n",c,sum);
else
printf("%c:sum %d is not divisible by 3\n",c,sum);
}
return 0;
}
int addDigits(int s)
{
int sum = 0;
while(s)
{
sum += (s%10);
s /= 10;
}
if(sum>9)
return addDigits(sum);
else
return sum;
}
as here i am keeping sum as single digit, so even with infinite length stream, overflow problem will not be there.
private static void IsDivisibleBy3()
{
int counter = 0;
bool evenOddFlag = true;
while (true)
{
var nextBit = Console.ReadKey().KeyChar;
if(nextBit == 'x')
break;
if (nextBit == '1')
{
counter += evenOddFlag ? 1 : -1;
}
evenOddFlag = !evenOddFlag;
if(nextBit == '0' || nextBit == '1')
Console.WriteLine(counter % 3 == 0 ? "\tDivisible" : "\tNot divisible");
else
Console.WriteLine("\tIncorrect bit value");
}
}
agree to the code of ashish..simple..but just one drawback..what happens when you run out of int and you have not found a single multiple of 3 so that num is not 0 anywhere...pasting my code...I have not dealt with endianness in this code i.e. right shifting will always mean a number multiplied by 2.
int main(void)
{
int bit;
short sum = 0;
int divisor;
scanf("%d",&bit);
while((bit == 0)||(bit == 1)) {
short t = 0;
t = sum << 1;
if(!sum)
sum = bit;
else if(t < 0) {
divisor = sum << 1;
sum = -1;
divisor = divisor % sum;
sum = divisor;
sum = (sum << 1) + bit;
}
else {
sum = (sum << 1) + bit;
}
if(sum %3 == 0) {
printf("\ndivisoble by 3\n");
sum = 0;
}
scanf("%d",&bit);
}
return 0;
}
#include <iostream>
using namespace std;
bool isDivisible(string stream, int divisor) {
int rem = 0;
string::iterator itr = stream.begin();
while(itr != stream.end()) {
rem = ( 2*rem + (int)(*itr - '0') ) % divisor;
itr++;
}
cout<<rem<<endl;
return rem == 0;
}
int main() {
string stream = "1001010110010101001010010100101001010100100101001010010101011101";
cout<<"isDivisible by 3 : "<<(isDivisible(stream, 3)? "true" : "false")<<endl;
return 0;
}
#include <iostream>
using namespace std;
bool isDivisible(string stream, int divisor) {
int rem = 0;
string::iterator itr = stream.begin();
while(itr != stream.end()) {
rem = ( 2*rem + (int)(*itr - '0') ) % divisor;
itr++;
}
cout<<rem<<endl;
return rem == 0;
}
int main() {
string stream = "1001010110010101001010010100101001010100100101001010010101011101";
cout<<"isDivisible by 3 : "<<(isDivisible(stream, 3)? "true" : "false")<<endl;
return 0;
}
here is my solutionn: the interviewer said it is fine.
int bit;
int num=0;
while(true){
scanf("%d",&bit);
if(bit==0){
num=num*2;
}
if(bit==1){
num=num*2+1;
}
if(bit!=0 && bit !=1){
printf("%s","invalid input.");
}
if(num%3==0){
num=0;
printf("%s","is divisible by 3");
}
else{
num=num%3;
printf("%s","not divisible by 3");
}
}
I think the key point here is that the stream is of *infinite* length.
- liangzhongliang March 26, 2012Any solution that keeps track of all bits or their summation or in any other form would cause overflow problems.
The solution needs some number theory to prevent keeping info of all incoming bits. The right way to do this is to only keep the REMAINDER.
Notice the truth that X%3 and X have the same remainder, when divided by 3. So having X%3 is enough to decide whether X is divisible by 3.
When new bit comes, multiply the remainder by 2 (if bit is 0) or *2+1 (if bit is 1). Then repeat the procedures of keeping remainders.