Find the repeating and missing numbers

[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]

Leave a Comment

Your email address will not be published. Required fields are marked *