Challenge: Sort the Marks

Lab C++ Beginner 10 points

Read marks (0 to 100) and print them sorted with counting sort, then the most common mark (smallest on a tie).

Input

Line 1: n. Line 2: n marks.

Output

Line 1: sorted marks. Line 2: Most common: <mark>

Example

Input

7
70 35 90 70 100 35 70

Output

35 35 70 70 70 90 100
Most common: 70

Sample input available Sample output available

Editor

C++

Hints

count[m]++ for each mark.

Walk from 0 to 100 printing each value count[v] times.

Solution explanation

O(n + 101) time.

Show solution

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

int main() {
    int n;
    cin >> n;
    vector<int> count(101, 0);
    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;
        count[m]++;
    }
    bool first = true;
    for (int v = 0; v <= 100; v++)
        for (int k = 0; k < count[v]; k++) {
            cout << (first ? "" : " ") << v;
            first = false;
        }
    cout << endl;
    int best = 0;
    for (int v = 0; v <= 100; v++)
        if (count[v] > count[best]) best = v;
    cout << "Most common: " << best << endl;
    return 0;
}

Output

Answer