Skills101
← All coding problems

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: n integers

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).

Loading editor…

Log in to run and submit your code — it's free.