def find_single_missing_integer( ArrayWithOneMissingItem ):
    # Returns the missing integer in 1..n given an array of size (n-1) containing all but one of those integers.
    n = len(ArrayWithOneMissingItem) + 1;
    running_sum = 0    

#  ALGORITHM:
#  We will iterate through array, keeping a running sum.
#  While we iterate we will subtract one number at a time from this sum from the list 1..n.   In this way we end up
#  having subtracted every number 1..n and will end up with the opposite (negative) of whatever number is missing.

#  In order to ensure that the running_sum does not overflow in the positive or negative direction as we do this,
#  we will take from the head (1,2,3...) of numbers to subtract if the running_sum is < 0 (to further reduce it as little as possible
#  so upcoming sums can make it positive again)
#  and from the tail (n, n-1, n-2...) if the running sum is positive, to reduce it as much as possible.  This can be thought of as trying,
#  within our algorithm, to stay as close to 0 as possible.

#  This will ensure we do not overflow at any point.

    #our head and tail "pointers" within every integer 1..n:
    all_ints_head=1
    all_ints_tail=n

    for element in ArrayWithOneMissingItem:
        if running_sum > 0: 
     # When the running sum is positive, we try to decrease it to be negative again.
     # logically,
     #   Add the current item to the running_sum,
     #   then you subtract the current tail of all numbers
     # But we combine these two into adding the difference:

            running_sum += (element - all_ints_tail);
            all_ints_tail -= 1; #decrement tail

        else:
            running_sum += (element - all_ints_head);
            all_ints_head += 1; #increment head

    #sanity check - these need to match after all this:
    assert(all_ints_head == all_ints_tail)


    #but we did not get a chance to subtract this last part from our list of all numbers.
    running_sum -= all_ints_head;
    
    #now we return the opposite (negative) of this running sum, which will be the single missing integer.
    return (-running_sum);



# This should be in a tester class, but this whole algorithm is so brittle, who cares.

myList=[1,2,3,5,6]

print "From ", myList, " the missing number is: ", find_single_missing_integer( myList )

myList=[2,3,4,5,6]

print "From ", myList, " the missing number is: ", find_single_missing_integer( myList )

myList=[1,2,3,4,5]

print "From ", myList, " the missing number is: ", find_single_missing_integer( myList )


myList=[6,5,4,3,1]

print "From ", myList, " the missing number is: ", find_single_missing_integer( myList )


myList=[1,2]

print "From ", myList, " the missing number is: ", find_single_missing_integer( myList )

myList=[2,1]

print "From ", myList, " the missing number is: ", find_single_missing_integer( myList )


myList=[1,3]

print "From ", myList, " the missing number is: ", find_single_missing_integer( myList )

myList=[2,3]

print "From ", myList, " the missing number is: ", find_single_missing_integer( myList )

myList=[1]

print "From ", myList, " the missing number is: ", find_single_missing_integer( myList )


myList=[2]

print "From ", myList, " the missing number is: ", find_single_missing_integer( myList )


myList=[1,2,4,5]

print "From ", myList, " the missing number is: ", find_single_missing_integer( myList )


myList=[2,3,4,5]

print "From ", myList, " the missing number is: ", find_single_missing_integer( myList )


myList=[1,2,3,4]

print "From ", myList, " the missing number is: ", find_single_missing_integer( myList )



myList=[5,4,3,2]

print "From ", myList, " the missing number is: ", find_single_missing_integer( myList )



myList=[5,4,3,1]

print "From ", myList, " the missing number is: ", find_single_missing_integer( myList )

From  [1, 2, 3, 5, 6]  the missing number is:  4
From  [2, 3, 4, 5, 6]  the missing number is:  1
From  [1, 2, 3, 4, 5]  the missing number is:  6
From  [6, 5, 4, 3, 1]  the missing number is:  2
From  [1, 2]  the missing number is:  3
From  [2, 1]  the missing number is:  3
From  [1, 3]  the missing number is:  2
From  [2, 3]  the missing number is:  1
From  [1]  the missing number is:  2
From  [2]  the missing number is:  1
From  [1, 2, 4, 5]  the missing number is:  3
From  [2, 3, 4, 5]  the missing number is:  1
From  [1, 2, 3, 4]  the missing number is:  5
From  [5, 4, 3, 2]  the missing number is:  1
From  [5, 4, 3, 1]  the missing number is:  2