A sorted array of roll numbers has repeats. Remove the duplicates in place, so each value appears once and the original order is kept. Print the new length, then the remaining values.
In C, write int dedupe(int *a, int n) that uses a read pointer and a write pointer, and returns the new length.
Constraints
- 0 ≤ n ≤ 200000
- −10^9 ≤ each value ≤ 10^9
- The input is sorted in non-decreasing order.
Input and output
- Input
- First line: n. Second line: n integers in non-decreasing order (absent when n = 0).
- Output
- First line: k, the number of distinct values. Second line: the k values, separated by spaces (an empty line when k = 0).
Examples
Input 1
7
1 1 2 3 3 3 9Output
4
1 2 3 9Values 1, 2, 3 and 9 remain.
Input 2
4
-5 0 0 12Output
3
-5 0 12The two zeros become one.
Show hints
- Equal values are next to each other because the array is sorted.
- Keep a write position. Copy an element there only when it differs from the last value you kept.
Show the explanation
Because the array is sorted, all copies of a value sit together. Walk it with two pointers:
readvisits every element once.writepoints one past the last value kept.
When *read != *(write - 1) the value is new, so copy it to *write and advance write. When the loop ends, write - a is the new length. The first element is always kept, and n == 0 must return 0 without touching memory.
This runs in O(n) time and O(1) extra space. Elements past index k are left as they were; the function only promises that the first k slots are correct. Pointer subtraction (write - a) gives a ptrdiff_t measured in elements, not bytes. Interviewers sometimes ask about that.
Original UniCircle question. Last reviewed 22 Oct 2026.