Quick Overview

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.

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

Company: Walmart Labs

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

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 ```python 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** ```text Input: nums = [4, 1, 3, 2, 4] Output: 4 ``` Here `n = 4`, and the value 4 appears twice. **Example 2** ```text Input: nums = [1, 1] Output: 1 ``` The smallest case: `n = 1`, so both entries must be 1. **Example 3** ```text 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.

Overview: 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 integer array `nums` of length `n + 1` in which every value lies 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. Every other value from `1` to `n` appears at most once, and some of them may not appear at all. Return the repeated value. **Rules** - Leave `nums` unchanged: do not sort it, overwrite entries, or mark entries in place. - Use only a constant amount of extra memory, one that does not grow with `n`: no set, dictionary, counting array, or copy of the input. **Example 1** ```text Input: nums = [4, 1, 3, 2, 4] Output: 4 ``` Here `n = 4`, and the value `4` appears twice. **Example 2** ```text 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. **Constraints** - `1 <= n <= 10^5` - `nums.length == n + 1` - `1 <= nums[i] <= n` - Exactly one value appears two or more times. Every value, including the answer, is at most `10^5`, so it never exceeds `2^31 - 1` (`int` is enough in Java and C++).

Constraints

  • 1 <= n <= 10^5
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • Exactly one value appears two or more times; every other value from 1 to n appears at most once, and some may not appear at all.
  • nums must be left unchanged, and extra memory must not grow with n.

Examples

Input: ([1, 1],)

Expected Output: 1

Explanation: Minimum valid input: n = 1, so both entries must be 1.

Input: ([4, 1, 3, 2, 4],)

Expected Output: 4

Explanation: Source example 1: n = 4, the repeated value equals n and sits at the first and last positions.

Hints

  1. There are n + 1 entries but only n possible values, so a repeat is guaranteed; think about what that same counting argument says about smaller ranges of values.
  2. Since nums is read-only and memory must stay constant, everything you track has to fit in a few integer variables, though reading the array several times is allowed.
  3. Every value lies between 1 and n, so each value is also a valid index into nums.

Loading coding console...

Show the approach

Approach

Treat the array as a function on indices, f(i) = nums[i], defined for i = 0..n. Every value lies in 1..n, so f maps the n + 1 indices into themselves, and the walk x0 = 0, x1 = f(x0), x2 = f(x1), ... must eventually revisit an index: it is a tail of length mu followed by a cycle of length lambda. No entry holds 0, so index 0 has no predecessor and lies on the tail (mu >= 1). The first cycle index e = x_mu is reached from two different indices, its predecessor on the tail and its predecessor on the cycle, and both hold the value e. So e is a repeated value, and because exactly one value repeats, e is the answer.

Phase 1 (Floyd's tortoise and hare): slow starts at x1 and fast at x2; each iteration moves slow one step and fast two, so after the loop slow = x_k and fast = x_2k for the first k >= 1 with x_k == x_2k. That k is a multiple of lambda with k >= mu, and such a k <= mu + lambda <= n + 1 exists, so the loop terminates.

Phase 2: start finder at x0 and advance finder and slow one step at a time. After j steps finder = x_j and slow = x_(k+j). When j = mu both equal x_mu = e, because k is a multiple of lambda and k >= mu. They cannot meet earlier: for j < mu the finder is still on the tail, while slow never leaves the cycle. Return finder.

Edge cases: n = 1 ([1, 1]) meets at once and returns 1; a self-loop (nums[k] == k on the walk) is a cycle of length 1; a value repeated three or more times only adds extra predecessors and does not change the cycle-entry argument. The array is only read, and three integer variables are used, which satisfies both rules.

Time complexity:
O(n)
Space complexity:
O(1)