Skip to main content

287. Find the Duplicate Number

mediumAsked at Bloomberg

An 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 Alex Chen, 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^5
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • All the integers in nums appear only once except for precisely one integer which appears two or more times.

Examples

Example 1

Input
nums = [1,3,4,2,2]
Output
2

Example 2

Input
nums = [3,1,3,4,2]
Output
3

Approaches

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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Find the Duplicate Number and other Bloomberg interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →