Remove Duplicates (sorted)

Lab Java Intermediate 20 points

Read a sorted array of n integers and print the distinct values in order, using two indexes (no collections).

Input

Line 1: n. Line 2: n integers.

Output

One line of distinct values.

Example

Input

8
1 1 2 3 3 3 4 5

Output

1 2 3 4 5

Sample input available Sample output available

Editor

Java

Hints

Keep a write index len; only write a value when it differs from the last written one.

Solution explanation

This in-place technique uses no extra memory - a classic interview problem.

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int len = 0;
        for (int i = 0; i < n; i++) {
            if (len == 0 || a[i] != a[len - 1]) {
                a[len++] = a[i];
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            sb.append(a[i]).append(i < len - 1 ? " " : "");
        }
        System.out.println(sb);
    }
}

Output

Answer