[MS][Adobe]Divisible by 3 or not
Given an infinite stream of bits with the bits being appended at the highest significant position. give an algorithm to to say whether the number formed by using the sequence of bits that had been processed till then, is divisible by 3 or not?
At any instant, num is the (number MODULUS 3) where number is decimal number formed till now from the input bits
ReplyDeleteInitially rem=0;
bool isDivisible(int bit,int rem)
{
rem*=2;
if(1==bit) rem+=1;
if(rem>3) rem-=3;
if(!rem) return true;
else return false;
}
Here Logic is :
At any instant, if the bit is 0, new_num = 2*prev_num
else new_num = 2*prev_num+1
Now check if it is divisible
@Navin i think you need to be little clear about what you explained. you have mentioned num but never used them, never mentioned of rem( Are you using as persist value across calls)
ReplyDeleteAlso "if the bit is 0, new_num = 2*prev_num" what does it mean initially if no is 1 and if bit 0 comes it will become 2. please explain your approach clearly.
@navin ahh i see you are considering the bit stream in reverse manner, anyway your approach is correct. you just need to correct the explanations.
ReplyDelete@Another way could be which can be applicable for checking the divisibility with any number.
ReplyDeleteconsider bits to appended left to right, so if '0' comes then '1' it should form "10" which is 2.
Algorithm: Consider the case for 3, any number when divided by 3 can have remainder as 0,1,-1. So a stream of number say "101" will give (2^2+ 2^0)%3 which is 2^2%3+ 2^0%3 = 1+1 = 2. You can do the same test for any number.
Simpler algo -- (number of bits in even position - number of bits) in odd places is always divisible by 3
ReplyDeleteex -- 1001 no of bits in even pos =1 (minus)- number of bits in odd places=1 = 0 so divisible by 3
21 :10101 3-0 = 3 is divisible by 3 so total number is divisible by 3