Find the missing number and repeated number

Question

I am practising interview questions from here.

Problem : You are given a read only array of n integers from 1 to n. Each integer appears exactly once except A which appears twice and B which is missing. Return A and B such that output A should precede B.

My approach :

Sum(Natural numbers) = Sum(given numbers) - A + B
Sum_squares(Natural numbers) = Sum_squares(given numbers) - A*A + B*B

where :

Sum of n Natural numbers is given by : n(n+1)/2
Sum of squares of n Natural numbers is given by : n((n+1)/2)((2n+1)/3)

The above two equations can be simplified to :

(B-A)  = Sum(Natural numbers) - Sum(given numbers) 
(B-A)*(B+A) = Sum_squares(Natural numbers) - Sum_squares(given numbers)

Solution:

def repeat_num_and_missing_num(array):
    """ returns the value of repeated number and missing number in the given array
    using the standard formulaes of Sum of n Natural numbers and sum of squares of n Natural Numbers"""
    missing_num = 0
    repeated_num = 0
    x = len(array)
    sum_of_num = 0
    sum_of_squares = 0
    sum_of_num_actual = (x*(x+1))/2
    sum_of_squares_actual = ((x)*(x+1)*(2*x+1) ) / 6

    for num in array:  
        sum_of_num += num
        sum_of_squares += num*num


    missing_num = (((sum_of_squares_actual - sum_of_squares) /(sum_of_num_actual - sum_of_num))
                    +(sum_of_num_actual - sum_of_num))/2 
    repeated_num = (((sum_of_squares_actual - sum_of_squares) /(sum_of_num_actual - sum_of_num))
                     -(sum_of_num_actual - sum_of_num))/2                  
    return repeated_num, missing_num

#Test Cases
print repeat_num_and_missing_num([5,3,2,1,1]) == (1,4)

print repeat_num_and_missing_num([1,2,3,4,5,16,6,8,9,10,11,12,13,14,15,16]) == (16,7)

print repeat_num_and_missing_num([1,1]) == (1,2)

How can I make this code better?

Answer 1

Removing trailing whitespace, renaming variables, reordering the code to group statements about the same concepts and introducing temporary variable to avoid writing and computing the same expressions multiple times and adding comments:

def repeat_num_and_missing_num(array):
    """ Return the value of repeated number and missing number in the given array
    using the standard formulaes of Sum of n Natural numbers and sum of squares of n Natural Numbers"""

    sum_of_num = 0
    sum_of_squares = 0
    for num in array:
        sum_of_num += num
        sum_of_squares += num*num

    x = len(array)
    sum_of_num_expected = (x * (x+1)) / 2
    sum_of_squares_expected = ((x) * (x+1) * (2*x+1)) / 6

    # Assuming A is present twice and B is missing:
    # B - A
    b_minus_a = sum_of_num_expected - sum_of_num
    # B^2 - A^2 = (B-A) * (B+A)
    b2_minus_a2 = sum_of_squares_expected - sum_of_squares
    # B + A
    b_plus_a = b2_minus_a2 / b_minus_a

    a = (b_plus_a - b_minus_a) / 2
    b = (b_plus_a + b_minus_a) / 2
    return a, b

Answer 2

In addition to what @Josay has already mentioned, I'd advise making use of the inbuilt sum function.

sum_of_num = sum(array)
sum_of_squared = sum((n*n for n in array))

which would be faster than a for-loop iterative solution.