Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Hashing & Two Pointers

Frequency of Elements

Easy · Hashing & Two Pointers · Asked at TCS, Infosys, Wipro, Accenture, Cognizant

Print every distinct value of the array together with how many times it appears, sorted by value.

Input

First line: n. Second line: n integers.

Output

One line per distinct value: value count, in increasing order of value.

Constraints

Example 1

Input

6
10 5 10 15 10 5

Output

5 2
10 3
15 1

Example 2

Input

1
7

Output

7 1

Hints

  1. Count each value with a map from value to count.
  2. The output must be sorted by value — use an ordered map (std::map / TreeMap) or sort the keys.

Approach

Insert every element into a map from value to count. A sorted map (std::map, TreeMap) gives the keys in increasing order. With a hash map, sort the keys before printing. Sorting the array and counting runs of equal values is another O(n log n) option.

Complexity: O(n log n) time · O(distinct values) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    map<long long, int> freq;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        freq[x]++;
    }
    for (auto &p : freq) cout << p.first << " " << p.second << "\n";
    return 0;
}

Python solution

import sys
from collections import Counter

data = list(map(int, sys.stdin.read().split()))
freq = Counter(data[1 : data[0] + 1])
print("\n".join(f"{v} {freq[v]}" for v in sorted(freq)))

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        TreeMap<Long, Integer> freq = new TreeMap<>();
        for (int i = 0; i < n; i++) freq.merge(sc.nextLong(), 1, Integer::sum);
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Long, Integer> e : freq.entrySet()) sb.append(e.getKey()).append(' ').append(e.getValue()).append('\n');
        System.out.print(sb);
    }
}

Solve Frequency of Elements online · All practice problems