Katkat
Back

Find the Single Repeated Value Among n + 1 Integers Drawn from 1 to n

Walmart LabsSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

Given an array of n + 1 integers whose values all lie between 1 and n, return the one value that repeats, possibly several times. The challenge is solving it without modifying the array and with constant extra memory, which rules out sorting, hash sets and counting arrays.

You are given an array nums of n + 1 integers, each between 1 and n inclusive. Because there are more entries than possible values, some value must appear more than once. The input guarantees that exactly one value is repeated, although it may appear two or more times. Return that value.

Solve it without modifying nums and using only a constant amount of extra memory.

Function Signature

def find_repeated(nums: list[int]) -> int:

Rules

  • nums must be left unchanged: do not sort it, overwrite entries, or mark entries in place.
  • Extra memory must not grow with n: no set, dictionary, counting array or copy of the input.
  • Every value from 1 to n other than the repeated one appears at most once, and some of them may not appear at all.

Constraints

  • 1 <= n <= 10^5 and len(nums) == n + 1
  • 1 <= nums[i] <= n
  • exactly one value appears two or more times

Examples

Example 1

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

Here n = 4, and the value 4 appears twice.

Example 2

Input: nums = [1, 1]
Output: 1

The smallest case: n = 1, so both entries must be 1.

Example 3

Input: nums = [5, 2, 5, 1, 5, 3]
Output: 5

Here n = 5; the value 5 appears three times and the value 4 does not appear at all.