InterviewBit – Repeat and Missing Number Array

Source: Repeat and Missing Number Array

Please Note:

There are certain problems which are asked in the interview to also check how you take care of overflows in your problem.
This is one of those problems.
Please take extra care to make sure that you are type-casting your ints to long properly and at all places. Try to verify if your solution works if number of elements is as large as 10⁵

Food for thought :

• Even though it might not be required in this problem, in some cases, you might be required to order the operations cleverly so that the numbers do not overflow.
  For example, if you need to calculate n! / k! where n! is factorial(n), one approach is to calculate factorial(n), factorial(k) and then divide them.
  Another approach is to only multiple numbers from k + 1 ... n to calculate the result.
  Obviously approach 1 is more susceptible to overflows.

---

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.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Note that in your output A should precede B.

Example:

Input:[3 1 2 5 3] 

Output:[3, 4] 

A = 3, B = 4

---

解題：

1. 這題其實用collections.defaultdict(int)非常好解，也可以控制在O(n)內，但題目已提到須在不使用額外記憶體的情況下做到linear runtime complexity，故此方式不可行（但最後我用Counter跑竟然過了……網站bug請勿模仿）；
2. 一開始會想到用factorial(n)的方式來算，再用n, n-1的降冪方式找出缺少跟多的數字，但這個方法的缺點是當n超過100甚至1000時，factorial(n)將變得異常肥大且難以執行運算（產生overflow），故不可行；
3. 一般狀態下，1~n的加總應為(n*(n+1))/2；跟目標陣列的差異為-A+B，也就是說
   • sum(Input) – (n*(n+1))/2 = A – B      (1)
     但要解一個二元一次方程式的未知數，我們還需要另一個算式來支持；
4. 這時就需要再把高中學過的累加平方和公式拿出來用了，若不熟悉該公式請參考堆積木計算級數的平方和或是平方數和與立方數和：
   • sum(Input^2) – (n(n+1)(2n+1))/6 = A^2 – B^2    (2)
5. 再來可以用(2)衍伸（A^2 – B^2 = (A+B)*(A-B)）得到A+B = (2)/(1)      (3)
   即可用聯立方程式求出我們所需的A跟B個別值

Code:

class Solution:
    # @param A : tuple of integers
    # @return a list of integers
    def repeatedNumber(self, A):
        
        n = len(A)
        
        sum_real =sum(A) 
        sum_square_real= 0
        
        for x in A:
            sum_square_real +=  x*x
            
        A_B = sum_real - (n*(n+1))//2
        
        
        A2_B2 = sum_square_real - (n*(n+1)*(2*n+1))//6
        
        A_plus_B = A2_B2/A_B
        
        missing = (abs(A_plus_B+A_B))/2
        
        repeat = (abs(A_plus_B - A_B))/2
        
        return [int(missing),int(repeat)]

GitHub: GitHub