Challenge: Class Election

Lab Java Beginner 10 points

Read n votes (one name per vote). Print the winner and their number of votes. If two or more names tie for the most votes, the winner is the one that comes first in alphabetical order.

Input

Line 1: n. Line 2: n names.

Output

<name> <votes>

Example

Input

6
Zara Ali Zara Ben Ali Zara

Output

Zara 3

Sample input available Sample output available

Editor

Java

Hints

Count with votes.put(name, votes.getOrDefault(name, 0) + 1).

When counts tie, a.compareTo(b) < 0 means a comes first alphabetically.

Solution explanation

Counting is O(n); finding the winner walks the map once. The tie rule makes the answer the same no matter what order the HashMap gives the keys.

Show solution

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        HashMap<String, Integer> votes = new HashMap<String, Integer>();
        for (int i = 0; i < n; i++) {
            String name = sc.next();
            votes.put(name, votes.getOrDefault(name, 0) + 1);
        }
        String winner = null;
        int most = 0;
        for (String name : votes.keySet()) {
            int v = votes.get(name);
            if (v > most || (v == most && name.compareTo(winner) < 0)) {
                winner = name;
                most = v;
            }
        }
        System.out.println(winner + " " + most);
    }
}

Output

Answer