Find the repeating and missing number

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.

#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;
}
import java.util.*;

class Solution {
    // Function to find repeating and missing numbers
    public int[] findMissingRepeatingNumbers(int[] nums) {
        int n = nums.length; // Size of the array
        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 new int[] {repeating, missing};
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 2, 5, 4, 6, 7, 5};
        
        // Create an instance of Solution class
        Solution sol = new Solution();

        int[] result = sol.findMissingRepeatingNumbers(nums);
        
        // Print the repeating and missing numbers found
        System.out.println("The repeating and missing numbers are: {" + result[0] + ", " + result[1] + "}");
    }
}
class Solution:
    # Function to find repeating and missing numbers
    def findMissingRepeatingNumbers(self, nums):
        
        # Size of the array
        n = len(nums) 
        repeating, missing = -1, -1

        # Find the repeating and missing number:
        for i in range(1, n + 1):
            # Count the occurrences:
            cnt = nums.count(i)

            # Check if i is repeating or missing
            if cnt == 2:
                repeating = i
            elif cnt == 0:
                missing = i

            """ If both repeating and missing
            are found, break out of loop"""
            if repeating != -1 and missing != -1:
                break

        # Return [repeating, missing]
        return [repeating, missing]

if __name__ == "__main__":
    nums = [3, 1, 2, 5, 4, 6, 7, 5]
    
    # Create an instance of Solution class
    sol = Solution()

    result = sol.findMissingRepeatingNumbers(nums)
    
    # Print the repeating and missing numbers found
    print(f"The repeating and missing numbers are: {{{result[0]}, {result[1]}}}")
class Solution {
    // Function to find repeating and missing numbers
    findMissingRepeatingNumbers(nums) {
        
        // Size of the array
        let n = nums.length; 
        let repeating = -1, missing = -1;

        // Find the repeating and missing number:
        for (let i = 1; i <= n; i++) {
            
            // Count the occurrences:
            let cnt = 0;
            for (let 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];
    }
}

const nums = [3, 1, 2, 5, 4, 6, 7, 5];

// Create an instance of Solution class
const sol = new Solution();

const result = sol.findMissingRepeatingNumbers(nums);

// Print the repeating and missing numbers found
console.log(`The repeating and missing numbers are: {${result[0]}, ${result[1]}}`);

Complexity Analysis

Time Complexity: O(N²), 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.

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.

#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;
}
import java.util.*;

class Solution {
    // Function to find repeating and missing numbers
    public int[] findMissingRepeatingNumbers(int[] nums) {
        
        // Size of the array
        int n = nums.length;
        
        // Hash array to count occurrences
        int[] hash = new int[n + 1];
        
        // 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 new int[]{repeating, missing};
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 2, 5, 4, 6, 7, 5};
        
        // Create an instance of Solution class
        Solution sol = new Solution();

        int[] result = sol.findMissingRepeatingNumbers(nums);
        
        // Print the repeating and missing numbers found
        System.out.println("The repeating and missing numbers are: {" + result[0] + ", " + result[1] + "}");
    }
}
class Solution:
    # Function to find repeating and missing numbers
    def findMissingRepeatingNumbers(self, nums):
        
        # Size of the array
        n = len(nums)
        
        # Hash array to count occurrences
        hash = [0] * (n + 1)
        
        # Update the hash array:
        for num in nums:
            hash[num] += 1

        repeating = -1
        missing = -1
        
        # Find the repeating and missing number:
        for i in range(1, n + 1):
            if hash[i] == 2:
                repeating = i
            elif hash[i] == 0:
                missing = i

            """ If both repeating and missing
            are found, break out of loop"""
            if repeating != -1 and missing != -1:
                break
        
        # Return [repeating, missing]
        return [repeating, missing]

if __name__ == "__main__":
    nums = [3, 1, 2, 5, 4, 6, 7, 5]
    
    # Create an instance of Solution class
    sol = Solution()
    
    result = sol.findMissingRepeatingNumbers(nums)
    
    # Print the repeating and missing numbers found
    print(f"The repeating and missing numbers are: {{{result[0]}, {result[1]}}}")
class Solution {
    // Function to find repeating and missing numbers
    findMissingRepeatingNumbers(nums) {
        
        // Size of the array
        let n = nums.length;
        
        // Hash array to count occurrences
        let hash = Array(n + 1).fill(0);
        
        // Update the hash array:
        for (let num of nums) {
            hash[num]++;
        }

        let repeating = -1, missing = -1;
        
        // Find the repeating and missing number:
        for (let 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];
    }
}
const nums = [3, 1, 2, 5, 4, 6, 7, 5];

// Create an instance of Solution class
const sol = new Solution();

const result = sol.findMissingRepeatingNumbers(nums);

// Print the repeating and missing numbers found
console.log(`The repeating and missing numbers are: {${result[0]}, ${result[1]}}`);

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.

Intuition

The optimal way is to convert the given problem into mathematical equations. Since we have two variables i.e. missing and repeating, try to form two linear equations & find the values of two variables using those equations.

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.

#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;
}
import java.util.*;

class Solution {
    // Function to find repeating and missing numbers
    public int[] findMissingRepeatingNumbers(int[] nums) {
        
        // Size of the array
        long n = nums.length;

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

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

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

        // Compute the difference values
        long val1 = S - SN;

        // S2 - S2n = X^2 - Y^2
        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 x = (val1 + val2) / 2;
        long y = x - val1;

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

    public static void main(String[] args) {
        int[] nums = {3, 1, 2, 5, 4, 6, 7, 5};

        // Create an instance of Solution class
        Solution sol = new Solution();

        int[] result = sol.findMissingRepeatingNumbers(nums);

        // Print the repeating and missing numbers found
        System.out.printf("The repeating and missing numbers are: {%d, %d}\n", result[0], result[1]);
    }
}
class Solution:
    # Function to find repeating and missing numbers
    def findMissingRepeatingNumbers(self, nums):
        
        # Size of the array
        n = len(nums)

        # Sum of first n natural numbers
        SN = (n * (n + 1)) // 2

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

        """ Calculate actual sum (S) and sum 
            of squares (S2) of array elements """
        S = 0
        S2 = 0
        for num in nums:
            S += num
            S2 += num * num

        # Compute the difference values
        val1 = S - SN

        # S2 - S2n = X^2 - Y^2
        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) """
        x = (val1 + val2) // 2
        y = x - val1

        # Return the results as [repeating, missing]
        return [int(x), int(y)]

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

# Create an instance of Solution class
sol = Solution()

result = sol.findMissingRepeatingNumbers(nums)

# Print the repeating and missing numbers found
print(f"The repeating and missing numbers are: {{{result[0]}, {result[1]}}}")
class Solution {
    // Function to find repeating and missing numbers
    findMissingRepeatingNumbers(nums) {
        // Size of the array
        let n = nums.length;

        // Sum of first n natural numbers
        let SN = (n * (n + 1)) / 2;

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

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

        // Compute the difference values
        let val1 = S - SN;

        // S2 - S2n = X^2 - Y^2
        let 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) */
        let x = (val1 + val2) / 2;
        let y = x - val1;

        // Return the results as [repeating, missing]
        return [Math.floor(x), Math.floor(y)];
    }
}

const nums = [3, 1, 2, 5, 4, 6, 7, 5];

// Create an instance of Solution class
const sol = new Solution();

const result = sol.findMissingRepeatingNumbers(nums);

// Print the repeating and missing numbers found
console.log(`The repeating and missing numbers are: {${result[0]}, ${result[1]}}`);

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.

Intuition

Another optimal solution is to use the XOR operation to find both the repeating and missing numbers. First, compute the XOR of the repeating number (X) and the missing number (Y). Determine the position of the first differing bit from the right between X and Y, which corresponds to the first set bit in (X^Y). Based on this position, group all elements (both from the array and from 1 to N) into two distinct groups. Identify which number belongs to the group where the first set bit is set, which indicates the repeating number, and the other number as the missing one.

Approach

For the first step, iterate and calculate the XOR of all the array elements and the numbers between 1 to N. Let’s call this value xr.

In order to find the position of the first set bit from the right, either use a loop or perform AND of the xr and negation of (xr-1) i.e. (xr & ~(xr-1)).

Now, take two variables i.e. zero and one & check the bit of that position for every element (array elements as well as numbers between 1 to N). If the bit is 1: We will XOR that element with variable one. If the bit is 0, XOR that element with variable zero.

Finally, we have two variables i.e. two numbers zero and one. Among them, one is repeating and the other is missing. It’s time to identify them.

Traverse the entire array and check how many times variable zero appears. If it appears twice, it will be the repeating number, otherwise, it will be the missing. Now, based on variable zero’s identity, determine in which category, variable one belongs.

#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 xr = 0;

        for (int i = 0; i < n; i++) {
            // XOR of all elements in nums
            xr = xr ^ nums[i]; 
            
            // XOR of numbers from 1 to n
            xr = xr ^ (i + 1);  
        }

        // Get the rightmost set bit in xr
        int number = (xr & ~(xr - 1));

        //Group the numbers based on the differentiating bit
        // Number that falls into the 0 group
        int zero = 0; 
        
        // Number that falls into the 1 group
        int one = 0;  

        for (int i = 0; i < n; i++) {
            
            /* Check if nums[i] belongs to the 1 group
            based on the differentiating bit*/
            if ((nums[i] & number) != 0) {
                
                // XOR operation to find numbers in the 1 group
                one = one ^ nums[i];
                
            } else {
                // XOR operation to find numbers in the 0 group
                zero = zero ^ nums[i]; 
            }
        }

        // Group numbers from 1 to n based on differentiating bit
        for (int i = 1; i <= n; i++) {
            
            /* Check if i belongs to the 1 group 
            based on the differentiating bit*/
            if ((i & number) != 0) {
                
                // XOR operation to find numbers in the 1 group
                one = one ^ i; 
                
            } else {
                // XOR operation to find numbers in the 0 group
                zero = zero ^ i; 
            }
        }

        // Count occurrences of zero in nums
        int cnt = 0; 

        for (int i = 0; i < n; i++) {
            if (nums[i] == zero) {
                cnt++;
            }
        }

        if (cnt == 2) {
            /*zero is the repeating number,
            one is the missing number*/
            return {zero, one}; 
        }
        
        /* one is the repeating number, 
        zero is the missing number*/
        return {one, zero}; 
    }
};

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;
}
import java.util.*;

class Solution {
    // Function to find repeating and missing numbers
    public int[] findMissingRepeatingNumbers(int[] nums) {
        // size of the array
        int n = nums.length; 

        int xr = 0;

        for (int i = 0; i < n; i++) {
            // XOR of all elements in nums
            xr = xr ^ nums[i]; 
            
            // XOR of numbers from 1 to n
            xr = xr ^ (i + 1);  
        }

        // Get the rightmost set bit in xr
        int number = (xr & ~(xr - 1));

        // Group the numbers based on the differentiating bit
        // Number that falls into the 0 group
        int zero = 0; 
        
        // Number that falls into the 1 group
        int one = 0;  

        for (int i = 0; i < n; i++) {
            /* Check if nums[i] belongs to the 1 group
            based on the differentiating bit*/
            if ((nums[i] & number) != 0) {
                // XOR operation to find numbers in the 1 group
                one = one ^ nums[i];
            } else {
                // XOR operation to find numbers in the 0 group
                zero = zero ^ nums[i]; 
            }
        }

        // Group numbers from 1 to n based on differentiating bit
        for (int i = 1; i <= n; i++) {
            
            /* Check if i belongs to the 1 group 
            based on the differentiating bit*/
            if ((i & number) != 0) {
                // XOR operation to find numbers in the 1 group
                one = one ^ i; 
            } else {
                // XOR operation to find numbers in the 0 group
                zero = zero ^ i; 
            }
            
        }

        // Count occurrences of zero in nums
        int cnt = 0; 

        for (int i = 0; i < n; i++) {
            if (nums[i] == zero) {
                cnt++;
            }
        }

        if (cnt == 2) {
            /*zero is the repeating number,
            one is the missing number*/
            return new int[] {zero, one}; 
        }
        
        /* one is the repeating number, 
        zero is the missing number*/
        return new int[] {one, zero}; 
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 2, 5, 4, 6, 7, 5};
        
        // Create an instance of Solution class
        Solution sol = new Solution();

        int[] result = sol.findMissingRepeatingNumbers(nums);
        
        // Print the repeating and missing numbers found
        System.out.println("The repeating and missing numbers are: {" + result[0] + ", " + result[1] + "}");
    }
}
class Solution:
    # Function to find repeating and missing numbers
    def findMissingRepeatingNumbers(self, nums):
        
        # size of the array
        n = len(nums)

        xr = 0

        for i in range(n):
            # XOR of all elements in nums
            xr = xr ^ nums[i] 
            
            # XOR of numbers from 1 to n
            xr = xr ^ (i + 1)  

        # Get the rightmost set bit in xr
        number = (xr & ~(xr - 1))

        # Group the numbers based on the differentiating bit
        # Number that falls into the 0 group
        zero = 0 
        
        # Number that falls into the 1 group
        one = 0  

        for i in range(n):
            """ Check if nums[i] belongs to the 1 group
             based on the differentiating bit"""
            if (nums[i] & number) != 0:
                
                # XOR operation to find numbers in the 1 group
                one = one ^ nums[i]
                
            else:
                # XOR operation to find numbers in the 0 group
                zero = zero ^ nums[i]

        # Group numbers from 1 to n based on differentiating bit
        for i in range(1, n + 1):
            
            # Check if i belongs to the 1 group 
            # based on the differentiating bit
            if (i & number) != 0:
                # XOR operation to find numbers in the 1 group
                one = one ^ i
                
            else:
                # XOR operation to find numbers in the 0 group
                zero = zero ^ i

        # Count occurrences of zero in nums
        cnt = 0

        for i in range(n):
            if nums[i] == zero:
                cnt += 1

        if cnt == 2:
            """ zero is the repeating number,
             one is the missing number"""
            return [zero, one]

        """ one is the repeating number, 
        zero is the missing number"""
        return [one, zero]

if __name__ == "__main__":
    nums = [3, 1, 2, 5, 4, 6, 7, 5]
    
    # Create an instance of Solution class
    sol = Solution()

    result = sol.findMissingRepeatingNumbers(nums)

    # Print the repeating and missing numbers found
    print(f"The repeating and missing numbers are: {{{result[0]}, {result[1]}}}")
class Solution {
    // Function to find repeating and missing numbers
    findMissingRepeatingNumbers(nums) {
        
        // size of the array
        let n = nums.length;

        let xr = 0;

        for (let i = 0; i < n; i++) {
            // XOR of all elements in nums
            xr = xr ^ nums[i]; 
            
            // XOR of numbers from 1 to n
            xr = xr ^ (i + 1);  
        }

        // Get the rightmost set bit in xr
        let number = (xr & ~(xr - 1));

        // Group the numbers based on the differentiating bit
        // Number that falls into the 0 group
        let zero = 0; 
        
        // Number that falls into the 1 group
        let one = 0;  

        for (let i = 0; i < n; i++) {
            /* Check if nums[i] belongs to the 1 group
            based on the differentiating bit*/
            if ((nums[i] & number) !== 0) {
                
                // XOR operation to find numbers in the 1 group
                one = one ^ nums[i];
                
            } else {
                // XOR operation to find numbers in the 0 group
                zero = zero ^ nums[i]; 
            }
        }

        // Group numbers from 1 to n based on differentiating bit
        for (let i = 1; i <= n; i++) {
            /* Check if i belongs to the 1 group 
            based on the differentiating bit*/
            if ((i & number) !== 0) {
                
                // XOR operation to find numbers in the 1 group
                one = one ^ i; 
                
            } else {
                // XOR operation to find numbers in the 0 group
                zero = zero ^ i; 
            }
        }

        // Count occurrences of zero in nums
        let cnt = 0; 

        for (let i = 0; i < n; i++) {
            if (nums[i] === zero) {
                cnt++;
            }
        }

        if (cnt === 2) {
            /*zero is the repeating number,
            one is the missing number*/
            return [zero, one]; 
        }
        
        /* one is the repeating number, 
        zero is the missing number*/
        return [one, zero]; 
    }
}

// Main function
let nums = [3, 1, 2, 5, 4, 6, 7, 5];

// Create an instance of Solution class
let sol = new Solution();

// Call findMissingRepeatingNumbers method
let result = sol.findMissingRepeatingNumbers(nums);

// Print the repeating and missing numbers found
console.log(`The repeating and missing numbers are: {${result[0]}, ${result[1]}}`);

Complexity Analysis

Time Complexity: O(N), using only one loop running for N times, where N is the size of the given array.

Space Complexity: O(1) no extra space is used.

Problem List

Find the repeating and missing number

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Complexity Analysis

Intuition

Approach

Complexity Analysis

Intuition

Approach

Complexity Analysis

Intuition

Approach

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts