Find the Repeating and Missing Number

Problem Statement:

You are given an integer array nums of size n containing values from the range [1, n]. Each value appears exactly once in the array except for two values:

One value (A) appears twice.
One value (B) is missing from the array.

Your task is to return these two values as an array of size 2, where:

A is the duplicate number (appears twice),
B is the missing number (does not appear in the array).

Constraints:

1 <= n <= 10^4
The array has exactly one duplicate and one missing number.

Examples

 Example 1:
 
 Input: nums = [3, 5, 4, 1, 1]
 Output: [1, 2]
 
 Explanation: 1 appears two times in the array and 2 is missing from nums.

Example 2:

Input: nums = [1, 2, 3, 6, 7, 5, 7]
Output: [7, 4]

Explanation: 7 appears two times in the array and 4 is missing from nums.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

The naive way is to count the occurrence in the given array using linear search, for each number between 1 to N. The element which occurs twice will be the repeating number and the number with 0 occurrence will be the missing number.

Approach:

Iterate in array from 1 to N & for each integer, i, count its occurrence in the given array using linear search.
Store those two elements that have the occurrence of 2 and 0. Finally, return the elements.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find repeating and missing numbers
    vector<int> findMissingRepeatingNumbers(vector<int>& nums) {
        
        // Size of the array
        int n = nums.size(); 
        int repeating = -1, missing = -1;

        // Find the repeating and missing number:
        for (int i = 1; i <= n; i++) {
            
            // Count the occurrences:
            int cnt = 0;
            
            for (int j = 0; j < n; j++) {
                if (nums[j] == i) cnt++;
            }

            // Check if i is repeating or missing
            if (cnt == 2) repeating = i;
            else if (cnt == 0) missing = i;

            /* If both repeating and missing
            are found, break out of loop*/
            if (repeating != -1 && missing != -1)
                break;
        }
        
        // Return {repeating, missing}
        return {repeating, missing};
    }
};

int main() {
    vector<int> nums = {3, 1, 2, 5, 4, 6, 7, 5};
    
    // Create an instance of Solution class
    Solution sol;

    vector<int> result = sol.findMissingRepeatingNumbers(nums);
    
    // Print the repeating and missing numbers found
    cout << "The repeating and missing numbers are: {" << result[0] << ", " << result[1] << "}\n";
    
    return 0;
}

Complexity Analysis:

Time Complexity: O(N^2), where N is the size of the array. Since we are using nested loops to count occurrences of every element between 1 to N.
Space Complexity: O(1) as no extra space is used.

2️⃣ Hashing (Better Approach)

Intuition:

The better way is, instead of counting the occurrences every time, use the hashing technique to store the frequency of each element between 1 to N. Now, the element with frequency 2 will be the repeating number and the element with frequency 0 will be the missing number.

Approach:

The range of the number is 1 to N, so declare a hash array of size N+1 (as we want to store the frequency of N as well).
Iterate all the elements of the given array and update the hash array when an element is encountered .
Now, iterate in the hash array and return the two elements with frequencies 2 and 0.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find repeating and missing numbers
    vector<int> findMissingRepeatingNumbers(vector<int>& nums) {
        
        // Size of the array
        int n = nums.size(); 
        
         // Hash array to count occurrences
        int hash[n + 1] = {0};
        
        // Update the hash array:
        for (int i = 0; i < n; i++) {
            hash[nums[i]]++;
        }

        int repeating = -1, missing = -1;
        
        // Find the repeating and missing number:
        for (int i = 1; i <= n; i++) {
            if (hash[i] == 2) {
                repeating = i;
            } else if (hash[i] == 0) {
                missing = i;
            }

            /* If both repeating and missing 
            are found, break out of loop*/
            if (repeating != -1 && missing != -1) {
                break;
            }
        }
        
        // Return {repeating, missing}
        return {repeating, missing};
    }
};

int main() {
    vector<int> nums = {3, 1, 2, 5, 4, 6, 7, 5};
    
    // Create an instance of Solution class
    Solution sol;

    vector<int> result = sol.findMissingRepeatingNumbers(nums);
    
    // Print the repeating and missing numbers found
    cout << "The repeating and missing numbers are: {" << result[0] << ", " << result[1] << "}\n";
    
    return 0;
}

Complexity Analysis:

Time Complexity: O(2*N), for using two loops each running for N times, where N is the size of the array.
Space Complexity: O(N) for using a hash array.

OR

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size(); // Get the size of the input array
        
        int dup     = -1; // Initialize variable to store the duplicate number
        int missing = -1; // Initialize variable to store the missing number
        
        // First pass: Find the duplicate by marking visited elements as negative
        for(int i = 0; i < n; i++) {
            int num = abs(nums[i]); // Get the absolute value of the current element
            
            // Check if the element at index 'num-1' is already negative
            // If it's negative, it means we've seen 'num' before, so it must be the duplicate
            if(nums[num - 1] < 0)
                dup = num; // Store the duplicate number
            else
                nums[num - 1] *= (-1); // Mark the element as visited by multiplying it by -1
        }
        
        // Second pass: Find the missing number by checking for positive values
        for(int i = 0; i < n; i++) {
            // If an element is positive, its index+1 is the missing number
            if(nums[i] > 0) {
                missing = i + 1; // Store the missing number
                break; // No need to check further once the missing number is found
            }
        }
        
        return {dup, missing}; // Return the duplicate and missing numbers as a vector
    }
};

Complexity Analysis:

Time Complexity:O(n)
- Because we iterate over the array twice, once for finding the duplicate and once for finding the missing number.
Space Complexity:O(1)
- Because we use constant extra space for the variables like dup and missing, and we modify the input array in-place.

3️⃣ Optimal (Mathematical Approach - Sum and Sum of Squares)

Intuition:

The problem can be viewed mathematically using the formulas for the sum of the first n natural numbers and the sum of squares of the first n natural numbers.

Let:

S be the sum of the given array,
S_actual = n*(n+1)/2 be the expected sum of numbers from 1 to n,
S_sq be the sum of squares of the given array,
S_sq_actual = n*(n+1)*(2*n+1)/6 be the expected sum of squares of numbers from 1 to n.

The difference between S_actual - S gives us the missing number minus the duplicate number (B - A), and similarly, using the difference of square sums, we can find the actual numbers.

Assuming the repeating number to be X and the missing number to be Y.

Step 1: Sum Equation

Now, we have the summation of the first n numbers is:

S = The summation of all elements in the given array.

S_actual = (n*(n+1))/2

S - S_actual = X - Y --------> equation 1
where, X = repeating number 
Y = missing number
S = sum of all elements in the array.
S_actual = sum of first n natural numbers.

Step 2: Square Sum Equation

Now, we know the summation of squares of the first n numbers is:

S_sq = The summation of squares of all the elements in the array
S_sq_actual = (n*(n+1)*(2n+1))/6

S_sq - S_sq_actual = X^2 - Y^2 ------------> equation 2
Where, S_sq = sum of squares of all elements in the array
S_sq_actual = sum of squares of first n natural numbers.

From equation 2 we can conclude,

S_sq - S_sq_actual = X^2 - Y^

From algebra, we know:
X^2 - Y^2 = (X-Y)(X+Y)
So, 
S_sq - S_sq_actual = (X - Y)(X + Y)

Let D = S - S_actual
Let S_sq_dif = S_sq - S_sq_actual
Then:
X + Y = S_sq_diff / D -------------------------> (equation 3)

Step 3: Solving for X and Y

Now, we have:
X - Y = D
X + Y = S_sq_diff / D

Adding the two equations:
2X = D + S_sq_diff/D
X = (D + S_sq_diff / D) / 2

Subtracting the two equations:
2Y = S_sq_diff / D - D
Y = (S_sq_diff/D - D) / 2

Final Formulas:

Let:

D = S − S_actual
This means D is the difference between the expected sum of numbers (S) and the actual sum you got from the array (S_actual).

S_sq_diff = S_sq − S_sq_actual
This means S_sq_diff is the difference between the expected sum of squares (S_sq) and the actual sum of squares from the array (S_sq_actual).

Now, we can use these values to find the repeating and missing numbers:

X (the repeating number) is calculated using:
X = (D + S_sq_diff / D) / 2

Y (the missing number) is calculated using:
Y = (S_sq_diff / D − D) / 2

So with the values of D and S_sq_diff, you can figure out which number is repeated and which one is missing in the array.

Dry Run:

      +-----+-----+-----+-----+-----+-----+-----+-----+
arr = |  3  |  1  |  2  |  5  |  4  |  6  |  7  |  5  |
      +-----+-----+-----+-----+-----+-----+-----+-----+
         0     1     2     3     4     5     6     7

n (size of arr) = 8

S (sum of the array) = 33
S_actual (Expected sum) = n*(n+1)/2 = 8*9/2 = 72/2 = 36
S_sq (Sum of squares of the given array) = 165
S_sq_actual = (n*(n+1)*(2n+1))/6 = 204

val1 = S - S_actual = 33 - 36 = -3
val2 = S_sq - S_sq_actual = -39

val2 = val1/val2 = -39/-3 = 12

x = (val1 + val2)/2 = 5 (Repeating)
y = x - val1 = 8 (Missing)

Approach:

First, find out the values of S and Sn, where S is the sum of all the elements of the array and Sn is the sum of natural numbers from 1 to N. Then calculate S - Sn and S - Sn = X - Y, where X is repeating number and Y is the missing number.
Next, find the values of S2 and S2n , where S2 is the summation of squares of all the elements in the given array and S2n is summation of squares of the first N numbers ((N*(N+1)*(2N+1))/6). Then calculate S2 - S2n and S2 - S2n = X2 - Y2.
From the above steps X + Y = (S2 - S2n) / (X-Y)
After performing steps 1 and 2, we will be having the values of X + Y and X - Y. Now, by substitution of values, we can easily find the values of X and Y. Finally, return X and Y.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find repeating and missing numbers
    vector<int> findMissingRepeatingNumbers(vector<int>& nums) {
        
        // Size of the array
        long long n = nums.size(); 

        // Sum of first n natural numbers
        long long SN = (n * (n + 1)) / 2;
        
        // Sum of squares of first n natural numbers
        long long S2N = (n * (n + 1) * (2 * n + 1)) / 6;

        /*Calculate actual sum (S) and sum 
        of squares (S2) of array elements*/
        long long S = 0, S2 = 0;
        for (int i = 0; i < n; i++) {
            S += nums[i];
            S2 += (long long)nums[i] * (long long)nums[i];
        }

        //Compute the difference values
        long long val1 = S - SN; 
        
        // S2 - S2n = X^2 - Y^2
        long long val2 = S2 - S2N; 

        //Calculate X + Y using X + Y = (X^2 - Y^2) / (X - Y)
        val2 = val2 / val1;

        /* Calculate X and Y from X + Y and X - Y
         X = ((X + Y) + (X - Y)) / 2
         Y = X - (X - Y)*/
        long long x = (val1 + val2) / 2;
        long long y = x - val1;

        // Return the results as {repeating, missing}
        return {(int)x, (int)y};
    }
};

int main() {
    vector<int> nums = {3, 1, 2, 5, 4, 6, 7, 5};
    
    // Create an instance of Solution class
    Solution sol;

    vector<int> result = sol.findMissingRepeatingNumbers(nums);
    
    // Print the repeating and missing numbers found
    cout << "The repeating and missing numbers are: {" << result[0] << ", " << result[1] << "}\n";
    
    return 0;
}

Complexity Analysis:

Time Complexity: O(N), as a single loop is used, where N is the size of the given array.
Space Complexity:O(1) no extra space is used.

4️⃣ Optimal Approach (XOR)

Intuition:

The XOR operation can be used to solve this problem because XOR has the property that x ^ x = 0 and x ^ 0 = x. By XORing all the elements of the array and the numbers from 1 to n, we can cancel out all numbers except the duplicate and missing ones.

Approach:

XOR all the numbers in the array and all numbers from 1 to n.
The result of the XOR operation will be A ^ B (the XOR of the duplicate and missing numbers).
Use a bitwise operation to separate the two numbers.

Code:

 class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int xorAll = 0, xorNums = 0;
        int n = nums.size();
        
        // XOR all numbers from 1 to n
        for (int i = 1; i <= n; i++) {
            xorAll ^= i;
        }
        
        // XOR all numbers in the nums array
        for (int num : nums) {
            xorNums ^= num;
        }
        
        // XOR of all elements and nums will give us (duplicate ^ missing)
        int xorResult = xorAll ^ xorNums;
        
        // Find the rightmost set bit
        int rightmostBit = xorResult & (-xorResult);
        
        // Separate numbers into two groups based on the rightmost set bit
        int group1 = 0, group2 = 0;
        for (int i = 1; i <= n; i++) {
            if (i & rightmostBit) {
                group1 ^= i;
            } else {
                group2 ^= i;
            }
        }
        
        for (int num : nums) {
            if (num & rightmostBit) {
                group1 ^= num;
            } else {
                group2 ^= num;
            }
        }
        
        // We have now either (duplicate, missing) or (missing, duplicate)
        // Check which is the duplicate
        for (int num : nums) {
            if (num == group1) {
                return {group1, group2};
            }
        }
        
        return {group2, group1};
    }
};

References

https://medium.com/@ganjinaveen2116193/missing-and-repeating-element-in-array-most-popular-interview-question-7f8cc9b0b9a6

Problem Statement:

Constraints:

Examples

Different Approaches

1️⃣ Brute Force Approach

Intuition:

Approach:

Code:

Complexity Analysis:

2️⃣ Hashing (Better Approach)

Intuition:

Approach:

Code:

Complexity Analysis:

OR

Complexity Analysis:

3️⃣ Optimal (Mathematical Approach - Sum and Sum of Squares)

Intuition:

Step 1: Sum Equation

Step 2: Square Sum Equation

Step 3: Solving for X and Y

Final Formulas:

Dry Run:

Approach:

Code:

Complexity Analysis:

4️⃣ Optimal Approach (XOR)

Intuition:

Approach:

Code:

References

About me

Popular Posts

Variadic Function Working in C

Understanding Complex C/C++ Declarations

How Characters are Stored in Memory

Quick links

Tags

Newsletter

🛠️ Settings

Problem Statement:

Constraints:

Examples

Different Approaches

1️⃣ Brute Force Approach

Intuition:

Approach:

Code:

Complexity Analysis:

2️⃣ Hashing (Better Approach)

Intuition:

Approach:

Code:

Complexity Analysis:

OR

Complexity Analysis:

3️⃣ Optimal (Mathematical Approach - Sum and Sum of Squares)

Intuition:

Step 1: Sum Equation

Step 2: Square Sum Equation

Step 3: Solving for X and Y

Final Formulas:

Dry Run:

Approach:

Code:

Complexity Analysis:

4️⃣ Optimal Approach (XOR)

Intuition:

Approach:

Code:

References

Variadic Function Working in C

Understanding Complex C/C++ Declarations

How Characters are Stored in Memory