Repeat and Missing Number Array

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
class Solution {
    public ArrayList<Integer> repeatedNumber(List<Integer> arr) {
        int n = arr.size();
        long sumLinear = 0;
        long sumSQ = 0;
        for (int i = 0; i < n; i++) {
            sumLinear += (long) arr.get(i);
            sumSQ += ((long) arr.get(i)) * ((long) arr.get(i));
        }
        long sumReqLin = (n * (n + 1)) / 2;
        long sumReqSQ = (n * (n + 1) * (2 * n + 1)) / 6;
        int x = (int) (((sumSQ - sumReqSQ) / (sumLinear - sumReqLin)) + (sumLinear - sumReqLin));
        x = x / 2;
        int y = (int) (x - (int) (sumLinear - sumReqLin));
        ArrayList<Integer> ans = new ArrayList<>();
        ans.add(x);
        ans.add(y);
        return ans;
    }
}

Last updated