Find Duplicates in an Array

You are given an array of integers of length \(n\) where each element is between 1 and \(n\) (inclusive). Some elements appear twice and others appear once. Your task is to find all the duplicate elements in the array.

Use the strategy of in-place indexing: for each number \(x\) in the array, check the element at index \(x-1\). If it is negative, then \(x\) is a duplicate; otherwise, mark it as visited by negating the value. Print all duplicates in the order they are discovered.

Note: The input is given via standard input (stdin) and the output should be printed to standard output (stdout). If there are no duplicates, print an empty line.

inputFormat

The first line contains an integer \(n\), representing the number of elements in the array. The second line contains \(n\) space-separated integers.

outputFormat

Print the duplicate numbers found in the array separated by a single space. If no duplicates exist, print an empty line.

8
4 3 2 7 8 2 3 1

2 3