287. Find the Duplicate Number
mediumAsked at BloombergAn array of n+1 integers in [1, n] contains exactly one duplicate. Find it without modifying the array and in O(1) extra space. Bloomberg uses this as a classic 'two constraints, no obvious trick' problem to see if you reach for Floyd's cycle detection.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Bloomberg loops.
- Glassdoor (2026-Q1)— Bloomberg SWE onsite reports cite this as a recurring 'multiple constraints' problem.
- Blind (2025-12)— Bloomberg new-grad reports highlight the O(1) space constraint as the actual grading criterion.
Problem
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums, return this repeated number. You must solve the problem without modifying the array nums and uses only constant extra space.
Constraints
1 <= n <= 10^5nums.length == n + 11 <= nums[i] <= nAll the integers in nums appear only once except for precisely one integer which appears two or more times.
Examples
Example 1
nums = [1,3,4,2,2]2Example 2
nums = [3,1,3,4,2]3Approaches
1. Floyd's cycle detection (tortoise + hare)
Treat indices as a linked list where i points to nums[i]. The duplicate creates a cycle. Use Floyd's to find the cycle entry.
- Time
- O(n)
- Space
- O(1)
function findDuplicate(nums) {
let slow = nums[0];
let fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow !== fast);
slow = nums[0];
while (slow !== fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}Tradeoff: The only O(n) time + O(1) space solution that doesn't modify the array. Bloomberg interviewers grade you on whether you reach for this when both constraints stack.
2. Binary search on value range
Binary search on [1, n]. For each mid, count how many nums are <= mid. If the count > mid, the duplicate is in [1, mid].
- Time
- O(n log n)
- Space
- O(1)
function findDuplicateBS(nums) {
let lo = 1, hi = nums.length - 1;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
let count = 0;
for (const v of nums) if (v <= mid) count++;
if (count > mid) hi = mid;
else lo = mid + 1;
}
return lo;
}Tradeoff: Slower than Floyd's but conceptually cleaner — works on the pigeonhole insight. Bloomberg sometimes accepts this if you don't recall Floyd's, but you must NAME the constraint that drives the choice.
Bloomberg-specific tips
Bloomberg interviewers grade specifically on the CONSTRAINT RECOGNITION. State: 'I can't modify the array and need O(1) space — that rules out sorting and rules out a hash set. The pigeonhole on indices gives me a linked list with a cycle, so Floyd's applies.' That reasoning is the actual signal.
Common mistakes
- Reaching for a hash set without noting the O(1) space constraint.
- Sorting (modifies the array — explicitly forbidden).
- Confusing the cycle-detection phase 1 (find meeting point) with phase 2 (find cycle entry from head).
Follow-up questions
An interviewer at Bloomberg may pivot to one of these next:
- Linked List Cycle (LC 141) — basic Floyd's, no value to return.
- Linked List Cycle II (LC 142) — return the cycle entry node.
- Missing Number (LC 268) — XOR or sum-formula trick.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does i -> nums[i] always produce a cycle?
Because there are n+1 positions but only n distinct values in [1, n]. Two positions map to the same next position — that's the cycle's entry.
When can I afford the binary-search version?
When you don't recall Floyd's. The binary-search version is O(n log n) — still passes the constraints. Always lead with Floyd's if you remember it.
Free learning resources
Curated free links for this problem.