Given an unsorted array nums of size n containing numbers from 1 to n, exactly one number appears twice and exactly one number is missing. Find the duplicate number and the missing number.
Example 1
Input: nums = [3, 1, 2, 5, 3]
Output: [3, 4]
Explanation: For n = 5, the expected values are 1, 2, 3, 4, 5. The value 3 occurs twice, while 4 is absent.
Example 2
Input: nums = [1, 1]
Output: [1, 2]
Explanation: For n = 2, the expected values are 1 and 2. The value 1 is repeated and 2 is missing.
Brute Force Approach
For each number from 1 to n, scan the array and count how many times that number appears. If it appears twice, it is the duplicate. If it does not appear at all, it is the missing number.
This approach's drawback is that the same input is scanned again for every possible number, so it becomes slow as the array grows.
Algorithm
Examine each expected value from
1throughn.For the current value, scan the complete array and count its occurrences.
Record the value when its count is
2, because it is the repeating number.Record the value when its count is
0, because it is the missing number.Stop once both answers are known; otherwise, the outer loop terminates after value
nand each inner scan terminates at the end of the array.Return the repeating number first and the missing number second. The same process handles the minimum valid size
n = 2.
Dry Run
Missing and Repeating number
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds the duplicate and missing numbers by counting every candidate. vector<int> findNumbers(vector<int>& nums) { int n = nums.size(); int repeating = -1; int missing = -1; // Count the occurrences of every expected value. for (int candidate = 1; candidate <= n; candidate++) { int frequency = 0; for (int value : nums) { // Increase the count when the current candidate is found. if (value == candidate) { frequency++; } } // Save a candidate that appears twice as the duplicate. if (frequency == 2) { repeating = candidate; } // Save a candidate that never appears as the missing number. else if (frequency == 0) { missing = candidate; } // No further candidates can change the unique answer. if (repeating != -1 && missing != -1) { break; } } return {repeating, missing}; }};// Driver codeint main() { vector<int> nums = {3, 1, 2, 5, 3}; // instance for class Solution Solution sol; vector<int> answer = sol.findNumbers(nums); cout << answer[0] << " " << answer[1] << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n²) because up to n candidates each trigger a scan of n elements n2
Space Complexity: O(1) auxiliary space because only counters and answer variables are stored.
Better Approach
The brute-force method counts the same elements many times. Instead of counting the frequency of each element one by one, a single traversal can store the frequency of every element.
Direct indexing is possible because every value lies between 1 and n. Each value can be used as an index in a frequency array.
After the traversal, an index with a count of 2 is the duplicate. An index with a count of 0 is the missing number. This approach is faster but requires an extra array.
Algorithm
Create a zero-filled frequency array of size
n + 1; index0remains unused.Traverse the input once and increment the position corresponding to each value.
Inspect frequency positions from
1throughnafter the counting pass ends.Record the index whose frequency is
2as the repeating number.Record the index whose frequency is
0as the missing number, and stop once both have been found.Return the two values in the required order. Direct indexing also handles
n = 2and missing boundary values without special cases.
Dry Run
hash
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds the duplicate and missing numbers using a frequency array. vector<int> findNumbers(vector<int>& nums) { int n = nums.size(); vector<int> frequency(n + 1, 0); // Store the count of each value at its matching index. for (int value : nums) frequency[value]++; int repeating = -1; int missing = -1; // Inspect all valid values to locate counts two and zero. for (int value = 1; value <= n; value++) { // A count of two identifies the duplicate number. if (frequency[value] == 2) { repeating = value; } // A count of zero identifies the missing number. else if (frequency[value] == 0) { missing = value; } // Stop after both required numbers have been found. if (repeating != -1 && missing != -1) { break; } } return {repeating, missing}; }};// Driver codeint main() { vector<int> nums = {3, 1, 2, 5, 3}; // instance for class Solution Solution sol; vector<int> answer = sol.findNumbers(nums); cout << answer[0] << " " << answer[1] << '\n'; return 0;}Complexity Analysis
Time Complexity: O(2 * n) because the input and the frequency array are each scanned once.
Space Complexity: O(n) auxiliary space for the frequency array.
Optimal Approach 1
Every number from 1 to n should appear exactly once. Therefore, the expected sum can be calculated with n(n + 1) / 2.
The given array contains one duplicate and one missing number. The sum of the array is the actual sum. Subtracting the expected sum from the actual sum gives duplicate - missing.
This first difference cannot find both numbers separately. A second difference is obtained by comparing the actual and expected sums of squared values.
Dividing the square-sum difference by the first difference gives duplicate + missing. The sum and difference of the two answers can then be used to find the duplicate and missing numbers.
Algorithm
Traverse the array once to calculate its sum and its sum of squares; the pass ends after all
nelements.Calculate the expected sum with
n(n + 1) / 2and the expected square sum withn(n + 1)(2n + 1) / 6.Subtract the expected sum from the actual sum to obtain
R - M. This difference cannot be zero for valid input.Subtract the expected square sum from the actual square sum, then divide by
R - Mto obtainR + M.Use the two equations to calculate
R, followed byM, and return them in that order.Use wide integer arithmetic before multiplication. The formulas require no separate boundary handling and remain valid for
n = 2.
Dry Run
Math approach
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds the duplicate and missing numbers using sums and square sums. vector<int> findNumbers(vector<int>& nums) { long long n = nums.size(); long long actualSum = 0; long long actualSquareSum = 0; // Accumulate the two actual totals using wide integers. for (long long value : nums) { actualSum += value; actualSquareSum += value * value; } long long expectedSum = n * (n + 1) / 2; long long expectedSquareSum = n * (n + 1) * (2 * n + 1) / 6; long long difference = actualSum - expectedSum; long long sumOfAnswers = (actualSquareSum - expectedSquareSum) / difference; // Use the sum and difference of the answers to find both numbers. long long repeating = (difference + sumOfAnswers) / 2; long long missing = repeating - difference; return {(int)repeating, (int)missing}; }};// Driver codeint main() { vector<int> nums = {3, 1, 2, 5, 3}; // instance for class Solution Solution sol; vector<int> answer = sol.findNumbers(nums); cout << answer[0] << " " << answer[1] << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n) because the array is traversed once.
Space Complexity: O(1) auxiliary space because a fixed number of totals is stored. JavaScript BigInt values have size-dependent internal storage, but no array-sized auxiliary structure is created.
Optimal Approach 2
Every number from 1 to n should appear once in the array. Consider the array and the complete range together. A correct number appears twice—once in each collection—so XOR cancels that pair.
The duplicate appears twice in the array and once in the complete range. Two copies cancel, leaving one copy of the duplicate. The missing number appears only in the complete range, so the missing number also remains. After all other pairs cancel, the result contains the duplicate and missing numbers combined through XOR.
The two remaining numbers must differ in at least one binary position. Any set bit in their combined XOR marks such a position: one number has 1 there, while the other has 0. Separating all values by that bit places the duplicate and missing numbers in different groups. Matching values still enter the same group and cancel.
The two group results are the required numbers, but their roles are not yet known. A final check in the original array identifies the value that occurs twice as the duplicate. The other value is the missing number. This approach keeps constant auxiliary space and avoids the overflow risk of square sums.
Algorithm
XOR all input values and all expected values from
1throughn. Both passes end afternvalues, leavingR XOR M.Isolate the rightmost set bit of that result; this bit must differ between the two unknown values.
Partition the input and the expected range by the isolated bit, XORing the two groups separately.
After both partition passes end, all correct pairs have cancelled, leaving
RandMin an unknown order.Scan the input once to determine which survivor occurs twice, then return it before the other survivor.
No special case is required for
n = 2or boundary values. The JavaScript implementation usesBigIntto avoid signed 32-bit bitwise coercion.
Dry Run
Optimal Xor approach
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds the duplicate and missing numbers by separating XOR results. vector<int> findNumbers(vector<int>& nums) { int n = nums.size(); int xorAll = 0; // Cancel all values that occur once in both collections. for (int value : nums) xorAll ^= value; for (int value = 1; value <= n; value++) xorAll ^= value; int rightmostSetBit = xorAll & -xorAll; int first = 0; int second = 0; // Partition the input according to the differing bit. for (int value : nums) { // Place the value in the group selected by the differing bit. if ((value & rightmostSetBit) != 0) { first ^= value; } else { second ^= value; } } // Partition the expected range in the same way. for (int value = 1; value <= n; value++) { // Place the value in the group selected by the differing bit. if ((value & rightmostSetBit) != 0) { first ^= value; } else { second ^= value; } } // Determine which survivor actually appears twice. int firstCount = 0; for (int value : nums) { // Count how often the first result appears in the input. if (value == first) { firstCount++; } } // Return the result that appears twice as the duplicate. if (firstCount == 2) { return {first, second}; } return {second, first}; }};// Driver codeint main() { vector<int> nums = {3, 1, 2, 5, 3}; // instance for class Solution Solution sol; vector<int> answer = sol.findNumbers(nums); cout << answer[0] << " " << answer[1] << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n) because a constant number of linear passes is made over the input and expected range.
Space Complexity: O(1) auxiliary space because only a fixed number of XOR accumulators and counters is used. JavaScript BigInt has size-dependent internal storage but does not create storage proportional to the array length.
Interview follow-up Questions
XOR separates the repeating and missing values but does not label them. Counting either survivor in the original array determines which one occurs twice.
Be the first to add a comment.