An array nums contains n + 1 integers, each between 1 and n, with exactly one repeated number. Return this number, which may appear more than twice.
Do not modify the array. Use constant extra space and less than O(n²) time.
Example 1
Input: nums = [4, 3, 1, 2, 3]
Output: 3
Explanation: The number 3 appears twice in the array.
Example 2
Input: nums = [2, 2, 2, 4, 1]
Output: 2
Explanation: The number 2 appears three times in the array.
Brute Force Approach
To find the duplicate number without modifying the array or using extra space, the duplicate can be reconstructed one binary digit at a time. Every number has a binary form containing 0s and 1s. Starting from the right, the positions have bit values 1, 2, 4, 8, and so on. For example, 3 is written as 011 because 0 × 4 + 1 × 2 + 1 × 1 = 3. Similarly, 4 is written as 100.
For each position, count how many array elements have 1 at that position. Compare this with the count among the numbers from 1 to n, taking each number once. If the array’s count is greater, the same position in the duplicate must be 1. Otherwise, that position remains 0. Repeating this comparison for every required position builds the complete duplicate number.
For example, consider [4, 3, 1, 2, 3]. The binary forms are [100, 011, 001, 010, 011]. The reference numbers [1, 2, 3, 4] have binary forms [001, 010, 011, 100]. In this example, the array contains those four numbers and one extra 3. Its binary form, 011, explains why extra 1s appear at the positions with bit values 1 and 2.
Start with the answer 000. At the rightmost position, with bit value 1, the array elements 3, 1, and 3 have 1. These are three separate occurrences, so the array’s count is 3. Among the reference numbers, only 1 and 3 have 1 at this position, giving a count of 2. Since 3 > 2, the rightmost answer digit becomes 1, changing the answer to 001.
At the middle position, with bit value 2, the qualifying array elements are 3, 2, and 3, giving a count of 3. The qualifying reference numbers are 2 and 3, giving a count of 2. Again, 3 > 2, so the middle answer digit becomes 1. The answer changes from 001 to 011.
At the position with bit value 4, only the number 4 has 1 in either group. Both counts are 1. The array’s count is not greater, so this answer digit stays 0. The completed answer is 011, which represents 2 + 1 = 3. Therefore, the duplicate number is 3.
Algorithm
Start with the duplicate number set to 0.
Check each bit position needed to represent n (corresponding to bit values 1, 2, 4, and so on).
Count how many array elements have a 1 at this bit position.
Count how many numbers from 1 to n have a 1 at this same bit position.
If the array’s count is greater, set this bit position to 1 in the duplicate number.
Return the duplicate number after checking all required bit positions.
Dry Run
Find the duplicate number - brute
Solution
#include<bits/stdc++.h>using namespace std;class Solution {public: // Reconstructs the duplicate by comparing counts at each bit position. int findDuplicate(const vector<int>& nums) { int n = nums.size() - 1; int duplicate = 0; for (int bit = 1; bit <= n; bit <<= 1) { int actual = 0; int expected = 0; // Count this bit in the given array. for (int value : nums) { if ((value & bit) != 0) { actual++; } } // Count the same bit among the numbers from 1 to n. for (int value = 1; value <= n; value++) { if ((value & bit) != 0) { expected++; } } // An excess means this bit is set in the duplicate. if (actual > expected) { duplicate |= bit; } } return duplicate; }};// Driver codeint main() { vector<int> nums = {4, 3, 1, 2, 3}; // Create an instance of class Solution. Solution sol; cout << sol.findDuplicate(nums) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(N log N). There are O(log N) relevant bit positions, and each requires scanning the array and the numbers from 1 to N.
Space Complexity: O(1) auxiliary space because only counters, the current bit, and the answer are stored.
Optimal Approach
Because every value in the array is between 1 and n, each number can be treated as a link pointing to another index in the array. For example, if nums[0] = 4, jumping to the value at index 0 leads to index 4 next. Starting from index 0 and repeatedly jumping to the index named by the current value creates a continuous path of indices, much like following nodes in a linked list. Since no value is 0, index 0 has no incoming links and safely serves as the starting point outside any loop.
Because a duplicate number appears at least twice in the array, at least two different positions hold that same value and therefore point to the exact same next index. Following the chain of links must eventually revisit that shared index and enter an endless cycle. For [4, 3, 1, 2, 3], the path of indices is 0 → 4 → 3 → 2 → 1 → 3 → …. Here, the cycle begins at index 3 because both index 4 and index 1 contain the value 3 and direct the path into index 3. Thus, the index where the cycle begins is the duplicate number itself.
Two pointers moving at different speeds can locate this cycle entry without modifying the array or storing visited positions. In the first phase, a slow pointer advances one link at a time while a fast pointer advances two links at a time. Once both pointers enter the cycle, the faster one closes the gap by one step on each move and is guaranteed to meet the slower one at some position inside the cycle.
Because the fast pointer traveled twice as far as the slow pointer before their first meeting, the distance from the start of the path to the cycle's entry matches the remaining distance along the cycle from their meeting point back to the entry. In the second phase, resetting one pointer back to the starting position while keeping the other at the meeting point, and then advancing both pointers one link at a time at the same speed, causes them to meet right at the cycle's entry. In the example [4, 3, 1, 2, 3], starting both pointers at nums[0] (index 4) causes them to first meet at index 1; after resetting one pointer to index 4 and moving both by one link, both land on index 3 in a single step, revealing 3 as the duplicate.
Detecting the cycle
Algorithm
Start both pointers at
nums[0], treating each value as the next index to visit.Move one pointer one link and the other two links repeatedly until they meet after moving.
Return one pointer to
nums[0]and leave the other at the meeting position.Advance both pointers one link at a time until they meet again.
Return the meeting index, which is the duplicate number.
Dry Run
Find the duplicate number - optimal
Solution
#include<bits/stdc++.h>using namespace std;class Solution {public: // Returns the repeated number without changing the array. int findDuplicate(const vector<int>& nums) { int slow = nums[0]; int fast = nums[0]; // Move one pointer one step and the other two steps until they meet. do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); // Restart one pointer at the beginning of the same path. fast = nums[0]; // Moving both one step at a time finds the cycle's entry. while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } // The cycle's entry is the duplicate number. return slow; }};// Driver codeint main() { vector<int> nums = {4, 3, 1, 2, 3}; // Create an instance of class Solution. Solution sol; cout << sol.findDuplicate(nums) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(N). Finding the first meeting and locating the cycle’s entry each require at most a linear number of pointer movements.
Space Complexity: O(1) auxiliary space because only two pointer positions are stored.
Interview follow-up Questions
Not reliably, because the repeated number may appear more than twice, leaving some other values absent. For [2, 2, 2, 4, 1], the array’s sum is 11, while 1 + 2 + 3 + 4 = 10. Their difference is 1, but the duplicate is 2.
Be the first to add a comment.