Repeat and Missing Number in Array Editorial

Practice Problem Link: Repeat and Missing Number in Array

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given a list nums of size n. Each number in nums lies from 1 to n.
Each integer appears exactly once, except x which appears twice, and y which doesn't appear at all.

Find x and y. Return them as an array [x, y].

Naive Approach

The naive approach is to just search for the missing number using 2 nested loops. For finding the repeated number, we can sort the array, and check which two adjacent elements are equal.

Analysis

• Time Complexity: O(n²)
• Space Complexity: O(1)

Implementation

C++

vector<int> findRepeatAndMissingNumber(vector<int> nums) {
    sort(nums.begin(), nums.end());
	int n = nums.size();
	vector<int> result;
	for(int i = 1; i < n; i++) {
		if(nums[i - 1] == nums[i]) {
			result.push_back(nums[i]);
		}
	}
	for(int i = 1; i <= n; i++) {
		if(find(nums.begin(), nums.end(), i) == nums.end()) {
			result.push_back(i);
			break;
		}
	}
	return result;
}

Java

class Solution {

    int[] findRepeatAndMissingNumber(int[] nums) {
        Arrays.sort(nums);
		int n = nums.length;
		int[] result = new int[2];
		for(int i = 1; i < n; i++) {
			if(nums[i - 1] == nums[i]) {
				result[0] = nums[i];
			}
		}
		for(int i = 1; i <= n; i++) {
			boolean possible = false;
			for(int j = 0; j < n; j++) {
				if(nums[j] == i) {
					possible = true;
					break;
				}
			}
			if(!possible) {
				result[1] = i;
				break;
			}
		}
		return result;
    }
}

Optimal Approach 

In the optimal approach we can use the following algorithm:

• Traverse the array and find the XOR of all the elements.
• XOR this value with all the elements in the permutation from  1 to n.
• Find the Least Significant Bit of this element.
• All the elements in the permutation from 1 to n which have this Bit set, as well as all the array elements with this bit set, are put in one group, and the rest of the elements in the other group.
• Taking Xor of all the elements in each group gives us our candidates for the repeating and missing element in the array.
• Now we can check which element is repeating and which is missing in linear time separately.

The idea of why this approach works is because, after step 2, all the bits set in XOR will be set in either the first set or the second but not both, because the permutation and the array elements have nullified each other. So, we can separate the elements into distinct sets.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

vector<int> findRepeatAndMissingNumber(vector<int> nums) {
    int xorOfArray = 0, n = nums.size();
		for(int i = 0; i < n; i++) {
			xorOfArray ^= nums[i];
		}
		for(int i = 1; i <= n; i++) {
			xorOfArray ^= i;
		}
		int index = (xorOfArray) & ~(xorOfArray - 1);
		int first = 0, second = 0;
		for(int i = 0; i < n; i++) {
			if(((index) & nums[i]) != 0) {
				first ^= nums[i];
			}
			else {
				second ^= nums[i];
			}
			if(((i + 1) & index) != 0) {
				first ^= i + 1;
			}
			else {
				second ^= i + 1;
			}
		}
		for(int i = 0; i < n; i++) {
			if(nums[i] == second) {
				int temp = first;
				first = second;
				second = temp;
				break;
			}
		}
		auto result = {first, second};
		return result;
}

Java

class Solution {
    int[] findRepeatAndMissingNumber(int[] nums) {
        int xor = 0, n = nums.length;
		for(int i = 0; i < n; i++) {
			xor ^= nums[i];
		}
		for(int i = 1; i <= n; i++) {
			xor ^= i;
		}
		int index = (xor) & ~(xor - 1);
		int first = 0, second = 0;
		for(int i = 0; i < n; i++) {
			if(((index) & nums[i]) != 0) {
				first ^= nums[i];
			}
			else {
				second ^= nums[i];
			}
			if(((i + 1) & index) != 0) {
				first ^= i + 1;
			}
			else {
				second ^= i + 1;
			}
		}
		for(int i = 0; i < n; i++) {
			if(nums[i] == second) {
				int temp = first;
				first = second;
				second = temp;
				break;
			}
		}
		int[] result = {first, second};
		return result;
    }
}