12. Find Duplicate in an Array of N+1 Integers

An array of size n+1 contains values from 1 to n, with exactly one value repeated (possibly more than once). Find and print that repeated value.

Input: The first line contains the array's size (n+1). The second line contains n+1 space-separated integers from 1 to n, with exactly one value repeated. Output: Print a single integer - the repeated value.

1 <= n <= 10^5

The problem's guarantee that values are always in the range 1..n (not arbitrary integers) is precisely what makes a fixed-size frequency array (indexed directly by value) a valid, efficient option here.

An array of size n+1 holds values from 1 to n, so by the pigeonhole principle at least one value must repeat - find it. Brute force: Compare every pair of elements directly to check for a match - this costs O(n²), unnecessarily slow when a single pass with a seen-set does the same job. Optimised: A single pass with a hash set (or a frequency array sized exactly to n, since values are guaranteed to be in the range 1..n) instantly flags a repeat the moment it's seen a second time - no need to compare every pair when you can just remember what you've already visited.

Compare every pair of elements in the array: for each index i, scan all later indices j and check if arr[i] equals arr[j]. Since exactly one value is guaranteed to repeat, this pairwise comparison will eventually find it. It is correct but examines roughly n^2/2 pairs even though the duplicate could be found much faster. Time: O(n^2) Space: O(1)

Treat the array as an implicit linked list where the value at each index points to the next index to visit (arr[i] is 'next' from i). Because values range from 1 to n in an array of size n+1, following these pointers is guaranteed to enter a cycle, and the node where the cycle begins is exactly the duplicated value (two different indices point to it). Running Floyd's tortoise-and-hare algorithm on this implicit list finds the cycle's entry point without any extra hash storage, matching the hash-set approach's linear time while using only constant space. Time: O(n) Space: O(1)

Walk through the array once, inserting each value into a hash set (or incrementing a counter in a frequency array of size n+1). The first value that is already present in the set/has a nonzero counter is the duplicate. This turns the pairwise comparison into a single linear pass with O(1) average lookups, at the cost of extra memory proportional to n. Time: O(n) Space: O(n)

1. Build a frequency count (or a 'seen' set) as you scan through the array. 2. The moment you encounter a value you've already recorded as seen, that's your duplicate - report it immediately. 3. If scanning with a full frequency array, simply look for the one value whose count is 2 or more after the full pass.

Time: O(n) - one single linear pass through the array. Space: O(n), for the seen-set or frequency array (though a clever O(1)-space cycle-detection technique, treating the array as a linked structure via index-hopping, exists as a well-known harder follow-up).

n = 1 (array size 2, values must both be 1); the repeated value occurring more than twice; and n = 10^5 (largest, confirming the frequency-count approach is O(n)).

Be ready to mention Floyd's cycle detection (the 'tortoise and hare' technique) as an O(1)-space alternative if asked to optimize space further - treating array values as 'next pointers' turns this into the exact same shape as detecting a cycle in a linked list.