Missing And Repeating

Time: O(n)

Space: O(1)

Intuition

Two equations: let x=missing, y=repeating. Sum difference: Sâˆ’S_expected = yâˆ’x. Sum of squares difference: S2âˆ’S2_expected = yÂ²âˆ’xÂ² = (yâˆ’x)(y+x). Solve for x and y.

Algorithm

1S=sum(arr), S_exp=n(n+1)/2. sumDiff=Sâˆ’S_exp = yâˆ’x.
2S2=sum(arr[i]Â²), S2_exp=n(n+1)(2n+1)/6. sq_diff=S2âˆ’S2_exp = yÂ²âˆ’xÂ².
3y+x = sq_diff/(y-x). Solve: y=(sumDiff+(y+x))/2, x=yâˆ’sumDiff.

Example Walkthrough

Input: arr=[3,1,3,4,5] (n=5)

1.S=16, S_exp=15. sumDiff=1=yâˆ’x.
2.S2=60, S2_exp=55. sqDiff=5=(yâˆ’x)(y+x)=1*(y+x) â†’ y+x=5.
3.y=3, x=2.

Output: Missing=2, Repeating=3

Common Pitfalls

•Use long arithmetic to avoid overflow in sum of squares.

Missing And Repeating.java

Java

// Approach: Math approach: use sum and sum of squares formulas, or XOR to find missing and repeating.
// Time: O(n) Space: O(1)
import java.util.*;

class Solve {
    int[] findTwoElement(int arr[]) {
        int n = arr.length;
        int[] result = new int[2];

        // Mark visited indices as negative
        for (int i = 0; i < n; i++) {
            int index = Math.abs(arr[i]) - 1;
            if (arr[index] < 0)
                result[0] = index + 1; // Repeating number
            else
                arr[index] *= -1;
        }

        // Find missing number
        for (int i = 0; i < n; i++) {
            if (arr[i] > 0) {
                result[1] = i + 1; // Missing number
                break;
            }
        }

        return result;
    }
}

class Solution {
    ArrayList<Integer> findTwoElement(int arr[]) {
        int[] n = new int[arr.length + 1];
        ArrayList<Integer> al = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            n[arr[i]]++;
        }

        for (int i = 1; i < n.length; i++) {
            if (n[i] == 2)
                al.add(i);
        }
        for (int i = 1; i < n.length; i++) {
            if (n[i] == 0)
                al.add(i);
        }
        return al;
    }
}

Was this solution helpful?