views:

5141

answers:

12

Write code to determine if a number is divisible by 3. The input to the function is a single bit, 0 or 1, and the output should be 1 if the number received so far is the binary representation of a number divisible by 3, otherwise zero.

Examples:

input  "0":       (0)  output 1
inputs "1,0,0":   (4)  output 0
inputs "1,1,0,0": (6)  output 1

This is based on an interview question. I ask for a drawing of logic gates but since this is stackoverflow I'll accept any coding language. Bonus points for a hardware implementation (verilog etc).

Part a (easy): First input is the MSB.

Part b (a little harder): First input is the LSB.

Part c (difficult): Which one is faster and smaller, (a) or (b)? (Not theoretically in the Big-O sense, but practically faster/smaller.) Now take the slower/bigger one and make it as fast/small as the faster/smaller one.

A: 

Actually the LSB method would actually make this easier. In C:

MSB method:

/* 
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_msb(char *input) {
  unsigned value = 0;
  char *p = input;
  if (*p == '1') {
    value &= 1;
  }
  p++;
  while (*p) {
    if (*p != ',') {
      value <<= 1;
      if (*p == '1') {
        ret &= 1;
      }
    }
    p++;
  }
  return (value % 3 == 0) ? 1 : 0;
}

LSB method:

/* 
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_lsb(char *input) {
  unsigned value = 0;
  unsigned mask = 1;
  char *p = input;
  while (*p) {
    if (*p != ',') {
      if (*p == '1') {
        value &= mask;
      }
      mask <<= 1;
    }
    p++;
  }
  return (value % 3 == 0) ? 1 : 0;
}

Personally I have a hard time believing one of these will be significantly different to the other.

cletus
Your solution uses O(n) memory... I mostly sure, that this is not what they expect
Artyom
+5  A: 

You need to do all calculations using arithmetic modulo 3. This is the way

MSB:

number=0
while(!eof)
    n=input()
    number=(number *2 + n) mod 3

if(number == 0)
    print divisible

LSB:

number = 0;
multiplier = 1;
while(!eof)
    n=input()
    number = (number + multiplier * n) mod 3
    multiplier = (multiplier * 2) mod 3

if(number == 0)
   print divisible

This is general idea...

Now, your part is to understand why this is correct.

And yes, do homework yourself ;)

Artyom
NB: multiplier will be always the sequence (1,2,1,2,...).
Anton Tykhyy
Interview question, not homework. It's just a puzzle, I aleady know the answer. How about part 3?
Eyal
Oops, I meant part c. Your solution for LSB, converted to any language or even hardware, uses more logic/code/time than your LSB solution. This is the hard part. Make LSB as good as MSB.
Eyal
@Eyal Buddy, I had given you an efficient solution... This is 99% of the job. Now optimize it. If two bits of memory make difference for you, try to find more tricks ;)
Artyom
Part c is the puzzle! That's the point! I have an LSB solution as fast as your MSB solution in any language you like. The puzzle is to find it.
Eyal
What, and you expect someone to solve that puzzle, that you happen to know the answer to already, in the middle of your interview while they're applying for a job? Heh. Did you figure it out in that situation?
apphacker
+2  A: 

The idea is that the number can grow arbitrarily long, which means you can't use mod 3 here, since your number will grow beyond the capacity of your integer class.

The idea is to notice what happens to the number. If you're adding bits to the right, what you're actually doing is shifting left one bit and adding the new bit.

Shift-left is the same as multiplying by 2, and adding the new bit is either adding 0 or 1. Assuming we started from 0, we can do this recursively based on the modulo-3 of the last number.

last | input || next | example
------------------------------------
0    | 0     || 0    | 0 * 2 + 0 = 0
0    | 1     || 1    | 0 * 2 + 1 = 1
1    | 0     || 2    | 1 * 2 + 0 = 2
1    | 1     || 0    | 1 * 2 + 1 = 0 (= 3 mod 3)
2    | 0     || 1    | 2 * 2 + 0 = 1 (= 4 mod 3)
2    | 1     || 2    | 2 * 2 + 1 = 2 (= 5 mod 3)


Now let's see what happens when you add a bit to the left. First, notice that:

22n mod 3 = 1

and

22n+1 mod 3 = 2

So now we have to either add 1 or 2 to the mod based on if the current iteration is odd or even.

last | n is even? | input || next | example
-------------------------------------------
d/c  | don't care | 0     || last | last + 0*2^n = last
0    | yes        | 1     || 0    | 0 + 1*2^n = 1 (= 2^n mod 3)
0    | no         | 1     || 0    | 0 + 1*2^n = 2 (= 2^n mod 3)
1    | yes        | 1     || 0    | 1 + 1*2^n = 2
1    | no         | 1     || 0    | 1 + 1*2^n = 0 (= 3 mod 3)
1    | yes        | 1     || 0    | 2 + 1*2^n = 0
1    | no         | 1     || 0    | 2 + 1*2^n = 1
Nathan Fellman
Next, convert all that stuff into a lookup table. For added speed, have the table look at more than one bit at once.
Brian
I didn't provide any code here. You're free to implement it any way you want.
Nathan Fellman
A: 

Read the following two bit-twiddling hacks:

They are not the answers you seek, but is probably of interest to you.

dirkgently
A: 

I think Nathan Fellman is on the right track for part a and b (except b needs an extra piece of state: you need to keep track of if your digit position is odd or even).

I think the trick for part C is negating the last value at each step. I.e. 0 goes to 0, 1 goes to 2 and 2 goes to 1.

Artelius
This is a hint: Your first sentence is wrong.
Eyal
+3  A: 

Here is an simple way to do it by hand. Since 1 = 22 mod 3, we get 1 = 22n mod 3 for every positive integer. Furthermore 2 = 22n+1 mod 3. Hence one can determine if an integer is divisible by 3 by counting the 1 bits at odd bit positions, multiply this number by 2, add the number of 1-bits at even bit posistions add them to the result and check if the result is divisible by 3.

Example: 5710=1110012. There are 2 bits at odd positions, and 2 bits at even positions. 2*2 + 2 = 6 is divisible by 3. Hence 57 is divisible by 3.

Here is also a thought towards solving question c). If one inverts the bit order of a binary integer then all the bits remain at even/odd positions or all bits change. Hence inverting the order of the bits of an integer n results is an integer that is divisible by 3 if and only if n is divisible by 3. Hence any solution for question a) works without changes for question b) and vice versa. Hmm, maybe this could help to figure out which approach is faster...

Accipitridae
+4  A: 

Heh

State table for LSB:

S I S' O
0 0 0  1
0 1 1  0
1 0 2  0
1 1 0  1
2 0 1  0
2 1 2  0

Explanation: 0 is divisible by three. 0 << 1 + 0 = 0. Repeat using S = (S << 1 + I) % 3 and O = 1 if S == 0.

State table for MSB:

S I S' O
0 0 0  1
0 1 2  0
1 0 1  0
1 1 0  1
2 0 2  0
2 1 1  0

Explanation: 0 is divisible by three. 0 >> 1 + 0 = 0. Repeat using S = (S >> 1 + I) % 3 and O = 1 if S == 0.

S' is different from above, but O works the same, since S' is 0 for the same cases (00 and 11). Since O is the same in both cases, O_LSB = O_MSB, so to make MSB as short as LSB, or vice-versa, just use the shortest of both.

Tordek
yeah, that's what I was looking for. The solution for MSB and LSB are the same. Almost no one every figures that out.
Eyal
+4  A: 

There's a fairly well-known trick for determining whether a number is a multiple of 11, by alternately adding and subtracting its decimal digits. If the number you get at the end is a multiple of 11, then the number you started out with is also a multiple of 11:

47278    4 - 7 + 2 - 7 + 8 = 0, multiple of 11     (47278 = 11 * 4298)
52214    5 - 2 + 2 - 1 + 4 = 8, not multiple of 11 (52214 = 11 * 4746 + 8)

We can apply the same trick to binary numbers. A binary number is a multiple of 3 if and only if the alternating sum of its bits is also a multiple of 3:

4   = 100       1 - 0 + 0 = 1, not multiple of 3
6   = 110       1 - 1 + 0 = 0, multiple of 3
78  = 1001110   1 - 0 + 0 - 1 + 1 - 1 + 0 = 0, multiple of 3
109 = 1101101   1 - 1 + 0 - 1 + 1 - 0 + 1 = 1, not multiple of 3

It makes no difference whether you start with the MSB or the LSB, so the following Python function works equally well in both cases. It takes an iterator that returns the bits one at a time. multiplier alternates between 1 and 2 instead of 1 and -1 to avoid taking the modulo of a negative number.

def divisibleBy3(iterator):

    multiplier = 1
    accumulator = 0

    for bit in iterator:
        accumulator = (accumulator + bit * multiplier) % 3
        multiplier = 3 - multiplier

    return accumulator == 0
Pourquoi Litytestdata
A: 

A number is divisible by 3 if the sum of it's digits is divisible by 3.
So you can add the digits and get the sum:
- if the sum is greater or equal to 10 use the same method
- if it's 3,6,9 then it is divisible
- if the sum is different than 3,6,9 then it's not divisible

However, the number is given in a binary representation. Your method works when the integer is in decimal representation. (And just for fun it can also be made to work hexadecimals)
Accipitridae
A: 

input "0": (0) output 1 inputs "1,0,0": (4) output 0 inputs "1,1,0,0": (6) output 1

shouldn't this last input be 12, or am i misunderstanding the question?

jim
Ahh.For the more general answer, here is a Discrete Finite Automata (general in the sense that a DFA can be created to describe any multiple of n, not just n=3)Q = q0 ... qn (in this case, n is three)the transition function, Delta: D (Qn, i) = Q 2n+i mod nq0 is the accept state.The key is to recognize that each new digit doubles the number (i=0) or doubles it and adds one (i=1). then, each state qn is a congruence class, meaning: q0 is the number mod n = 0, q1 is the number mod n = 1, etc.In defense of the interviewing guy, this question actually did help me out with homework.
jim
no formatting, apologies folks
jim
+4  A: 

Here... something new... how to check if a binary number of any length (even thousands of digits) is divisible by 3.

alt text

-->((0))<---1--->()<---0--->(1)        ASCII representation of graph

From the picture.

1) You start in the double circle. 2) When you get a one or a zero, if the digit is inside the circle, then you stay in that circle. However if the digit is on a line, then you travel across the line. 3) Repeat step two until all digits are comsumed. 4) If you finally end up in the double circle then the binary number is divisible by 3.

You can also use this for generating numbers divisible by 3. And i wouldn't image it would be hard to convert this into a circuit.

1 example using the graph...

11000000000001011111111111101 is divisible by 3 (ends up in the double circle again)

Try it for yourself.

You can also do similar tricks for performing MOD 10, for when converting binary numbers into base 10 numbers. (10 circles, each doubled circled and represent the values 0 to 9 resulting from the modulo)

EDIT: This is for digits running left to right, its not hard to modify the finite state machine to accept the reverse language though.

NOTE: In the ASCII representation of the graph () denotes a single circle and (()) denotes a double circle. In finite state machines these are called states, and the double circle is the accept state (the state that means its evenually divisible by 3)

clinux