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.
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;
}
}