Find the Duplicate Number (Cyclic Sort approach)

Problem

Given an array of n+1 integers where each integer is in the range [1, n], find the duplicate number. You must not modify the array and must use O(1) extra space. The cyclic-sort approach leverages the fact that each number belongs at a specific index.

Constraints

• ›2 ≤ n ≤ 10⁵
• ›1 ≤ nums[i] ≤ n − 1
• ›Must not modify the array; O(1) extra space