Medium · Counting arrays

Digit Frequency

For each digit that appears in a number, print how many times. Your first counting array — the pattern behind histograms and voting counts.

At a glanceCount each digit in a 10-slot array, then print only the digits that appeared, as digit:count in ascending order — a fixed bucket array instead of sorting.

Problem

Input: One non-negative integer (0 <= n <= 1000000000).

Output: One line per occurring digit: digit:count, in ascending order.

Sample:

InputOutput
1223331:1
2:2
3:3

Your solution

main.cpp — your solution
Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Array as counters

int count[10] = {0}; then count[n % 10]++; each time you chop a digit.

Hint 2 — Only print what exists

Loop the ten digits and print only when count[d] > 0 — printing zero counts fails the judge.

Solution (try it first!) 
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int count[10] = {0};
    while (n > 0) {
        count[n % 10]++;
        n /= 10;
    }
    for (int d = 0; d <= 9; d++) {
        if (count[d] > 0) cout << d << ":" << count[d] << endl;
    }
    return 0;
}

This is the pattern behind counting sort and histograms: index by value, count by increment. Compare with the two-bucket version.

Deep dive

Why this works

A count array indexed by value is the simplest hash table in existence: no hashing, no collisions, O(1) lookup by construction.

The cost

O(n + 10) time, O(10) space. The constant 10 is why this beats sorting by a mile.

Where it goes wrong

  • Indexing with a char uses its ASCII code (57 for '9'), not 9. Subtract '0'.
  • Printing all ten buckets instead of only those that occurred fails the exact-output diff.

Next step

Same array, different aggregation: Sum a Matrix.

Two things to remember

  • Value-as-index is a hash table with no hash.
  • '9' - '0' == 9 — the ASCII offset is the whole trick.
🐞 This version fails — open it and try

Prints all ten buckets instead of only the digits that appear

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int count[10] = {0};
    while (n > 0) {
        count[n % 10]++;
        n /= 10;
    }
    for (int d = 0; d <= 9; d++) {
        cout << d << ":" << count[d] << endl;
    }
    return 0;
}