101
0/320
Loading content...
You are given an array nums containing n + 1 integers, where each integer is within the inclusive range [1, n]. This configuration guarantees by the Pigeonhole Principle that at least one value must appear more than once.
Your objective is to identify and return the value that is repeated in the array.
Critical Constraints:
This problem challenges you to think creatively about cycle detection algorithms and mathematical properties of the input structure to find the duplicate without the typical tools like sorting or hashing.
nums = [1,3,4,2,2]2The value 2 appears twice in the array while all other values (1, 3, 4) appear exactly once. The array has 5 elements (n+1 = 5, so n = 4), and all values are in range [1, 4].
nums = [3,1,3,4,2]3The value 3 appears at indices 0 and 2, making it the duplicate. With n = 4, all values must be in [1, 4], and 3 is the one that repeats.
nums = [3,3,3,3,3]3The value 3 appears five times. Note that the problem guarantees at least one repeat, but a value may repeat many more times. Here, 3 is the only value present, and it satisfies the constraint since 3 is within [1, 4].
Constraints