Challenge: Remove the Bad Apples

Lab Java Beginner 10 points

A crate holds n apples with weights. Remove every apple whose weight equals bad, keeping the others in order. Do it in place in one pass: keep a “write” index for where the next good apple goes. Print how many are left, then the weights (print empty if none are left).

Input

Line 1: n bad. Line 2: n whole numbers.

Output

Line 1: the count left. Line 2: the remaining weights, or empty.

Example

Input

7 3
3 1 3 2 3 3 5

Output

3
1 2 5

Sample input available Sample output available

Editor

Java

Hints

read looks at every apple; write marks the next free spot for a good apple.

At the end, write is the number of good apples.

Solution explanation

Calling list.remove() for each bad apple would shift the list again and again: O(n²). The read/write trick touches each apple once: O(n) time, O(1) extra memory.

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(), bad = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        int write = 0;
        for (int read = 0; read < n; read++) {
            if (a[read] != bad) {
                a[write] = a[read];
                write++;
            }
        }
        System.out.println(write);
        if (write == 0) {
            System.out.println("empty");
            return;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < write; i++) {
            if (i > 0) sb.append(' ');
            sb.append(a[i]);
        }
        System.out.println(sb);
    }
}

Output

Answer