[Question]:Given an unsorted array of size n. Array elements are in the range of 1 to n. One number from set {1, 2, …n} is missing and one number occurs twice in the array. Find these two numbers.
Input: arr[] = {3, 1, 3}
Output: Missing = 2, Repeating = 3
Explanation: In the array, 2 is missing and 3 occurs twice
Input: arr[] = {4, 3, 6, 2, 1, 1}
Output: Missing = 5, Repeating = 1
Time Complexity: O(N), where N = the size of the given array. Reason: We are using only one loop running for N times. So, the time complexity will be O(N). Space Complexity: O(1)
func findMissingRepeatingNumbers(_ a: [Int]) -> [Int] {
let n = a.count; // size of the array
// Find Sn and S2n:
var SN = (n * (n + 1)) / 2;
var S2N = (n * (n + 1) * (2 * n + 1)) / 6;
// Calculate S and S2:
var S = 0, S2 = 0;
for i in 0..<n {
S += a[i];
S2 += a[i] * a[i];
}
//S-Sn = X-Y:
var val1 = S - SN;
// S2-S2n = X^2-Y^2:
var val2 = S2 - S2N;
//Find X+Y = (X^2-Y^2)/(X-Y):
val2 = val2 / val1;
//Find X and Y: X = ((X+Y)+(X-Y))/2 and Y = X-(X-Y),
// Here, X-Y = val1 and X+Y = val2:
let x = (val1 + val2) / 2;
let y = x - val1;
return [x, y];
}
var mixArrayForMissingRepeating = [3, 1, 2, 5, 4, 6, 7, 5];
var missingAndRepeating = findMissingRepeatingNumbers(mixArrayForMissingRepeating);
print("Misssing & repeating numbers are-->", missingAndRepeating) // [5, 8]