import random
import timeit

MAXI = 100000
numbers = list(range(1, MAXI + 1))
excluded_nr = random.randint(1, MAXI + 1)
numbers.remove(excluded_nr)
random.shuffle(numbers)

def first_method():
    bits = [False] * MAXI
    for nr in numbers:
        bits[nr-1] = True
    print 'Missing number is %d' % (bits.index(False) + 1)

def second_method():
    total_sum = MAXI * (MAXI+1) / 2
    for nr in numbers:
        total_sum -= nr
    print 'Missing number is %d' % total_sum

def third_method():
    sorted_numbers = sorted(numbers)
    for i in range(1, MAXI):
        if sorted_numbers[i-1] != i:
            print 'Missing number is %d' % i
            return

def fourth_method():
    total = 0
    for nr in numbers:
        if nr % 2 == 0:
            total -= nr
        else:
            total += nr
    print 'Missing number is %d' % abs(total + MAXI/2)


def fifth_method():
    all_xor = 0

    for nr in numbers:
        all_xor ^= nr

    print 'Missing number is %d' % (all_xor ^ MAXI)


methods = [
  first_method,
  second_method,
  third_method,
  fourth_method,
  fifth_method
]

for method in methods:
    start = timeit.default_timer()
    method()
    elapsed = timeit.default_timer() - start
    print 'Elapsed time: %.4f' % elapsed