Find All Duplicates
easyArrays & Prefix Sums+10 XPTime limit 2s
An array has n numbers, each between 1 and n. Every value appears once or twice. Print every value that appears twice.
Input:
- line 1:
n - line 2:
nintegers
Output: the repeated values in increasing order, separated by spaces — or -1 if there are none.
Constraints: 1 ≤ n ≤ 10⁵, 1 ≤ a[i] ≤ n.
Think about it: a count array or hash set is easy. For O(1) extra space, use the array itself: for each value v, look at position v − 1. If that cell is still positive, make it negative ("I've seen v"); if it is already negative, v is a duplicate.
Sample input 1
8 4 3 2 7 8 2 3 1
Sample output 1
2 3
Sample input 2
3 1 2 3
Sample output 2
-1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).