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 Sam K., 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

More Bit Manipulation practice problems

See all Bit Manipulation problems →