Challenge: Zeros to the Back

Lab C++ Beginner 10 points

Read n numbers and move all zeros to the end, keeping the order of the others, in place with a slow and a fast pointer. Print the result separated by spaces.

Input

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

Output

The rearranged numbers.

Example

Input

5
0 5 0 3 12

Output

5 3 12 0 0

Sample input available Sample output available

Editor

C++

Hints

slow = where the next non-zero belongs.

When v[fast] != 0, swap it to position slow and move slow on.

Solution explanation

Non-zero numbers move forward in their original order; zeros drift to the back.

Show solution

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int& x : v) cin >> x;
    int slow = 0;
    for (int fast = 0; fast < n; fast++)
        if (v[fast] != 0) swap(v[slow++], v[fast]);
    for (int i = 0; i < n; i++) cout << v[i] << (i + 1 < n ? " " : "\n");
    return 0;
}

Output

Answer