Skip to main content

287. Find the Duplicate Number

medium

Find the single repeated number in an array of n+1 integers in the range [1, n]. The bit-counting approach: for each bit position, compare set counts in nums vs. 1..n.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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

Example 3

Input
nums = [3,3,3,3,3]
Output
3

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Sorting modifies the array. A hash set takes O(n) space. Both are forbidden by the constraints.

Hint 2

Floyd's tortoise-and-hare on the index→value mapping works in O(n)/O(1) — but the bit-counting alternative is more bit-focused.

Hint 3

Bit-counting trick: for each bit position b, count how many elements of nums have bit b set, versus how many integers in [1..n] have bit b set. The duplicate's contribution biases one count over the other.

Solution approach

Reveal approach

Bit-counting approach. For each bit position b from 0 to 31, compute nums_count = number of elements in nums with bit b set, and base_count = number of integers in [1..n] with bit b set. If the duplicate value d has bit b set, then nums has one extra instance with bit b set compared to the baseline 1..n: nums_count - base_count >= 1. If d does NOT have bit b set, the duplicate replaces a value, but since each non-duplicate value appears exactly once in both nums and 1..n, nums_count <= base_count. Set bit b of the answer iff nums_count > base_count. Total time O(32n) ≈ O(n), space O(1). Floyd's cycle-detection is the canonical O(n)/O(1) alternative; the bit-counting solution is the more bit-manipulation-focused angle.

Complexity

Time
O(n log n)
Space
O(1)

Related patterns

  • bit-manipulation
  • two-pointers
  • binary-search

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Find the Duplicate Number and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →