Find All Duplicates in an Array

Given an array of integers, where each integer is in the range 1 to n, some elements appear exactly twice and others appear once. Your task is to find all the integers that appear twice.

The algorithm must run in linear time \(O(n)\) and use only constant extra space. Hint: You can modify the input array in-place.

Examples:

• Input: 4 3 2 7 8 2 3 1 → Output: 2 3
• Input: 1 1 2 → Output: 1
• Input: 1 → Output: (empty)

inputFormat

The first line of the input contains an integer n (\(1 \le n \le 10^5\)), which is the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Output the duplicate numbers in ascending order, separated by a single space. If there are no duplicates, output an empty line.

8
4 3 2 7 8 2 3 1

2 3