gXa's blog

Interview Question

By gXa, history, 6 years ago, In English

There are 3 integers a, b, w.

There are 2 equations –

w+a=b

a (bitwise AND) b = 0;

I was given the value of w and he asked me to calculate the number of pairs (a, b) satisfying the two equations.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Let i be the left-most set bit in m (0 -based), then for ever a = "111111111..00000", where 1 appears aleast two times, and zero appears i times, then a&b = a&(a + w) = 0

Therefore the number of solutions is ∞ (for positive w).

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you are right that is why I am asking about constraints.

    constraints?

    → Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I guess the first equation should look like a + b = w instead of a + w = b.

In case of a + b = w
In case of a + w = b
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What if there is a limit for case a + w = b

    → Reply