Facebook Interview Questions/Q 3

From Software Engineers Wiki
Jump to: navigation, search

Given n, return 1 ^ 2 ^ 3 ^ ... ^ n, where ^ is binary xor.

Answer

We find cyclic pattern with xor operations.

  • 0 ^ 1 = 1
  • 1 ^ 2 = 3
  • 3 ^ 3 = 0
  • 0 ^ 4 = 4
  • 4 ^ 5 = 1
  • 1 ^ 6 = 7
  • 7 ^ 7 = 0
  • 0 ^ 8 = 8

In general, it follows following cycle.

  • 0 ^ n = n
  • (n - 1) ^ (n) when n is multiple of 4 + 1: n - 1 = 0bXXXX00, n = 0bXXXX01. So (n - 1) ^ (n) = 1
  • 1 ^ (n) when n is multiple of 4 + 2: n = 0bXXXX10. 1 ^ n = 0bXXXX11 = n + 1
  • n ^ n = 0
def return_n(n):
        return n
def return_1(n):
        return 1
def return_n_plus_1(n):
        return n + 1
def return_0(n):
        return 0

def xor_until_n(n):
        func_list = {
                0: return_n,
                1: return_1,
                2: return_n_plus_1,
                3: return_0,
        }
        func = func_list.get(n % 4)
        return func(n)

def main():
        for i in range(1, 16):
                print '{0} : {1}'.format(i, xor_until_n(i))

main()
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox