Medio · Arrays de conteo

Frecuencia de dígitos

Para cada dígito presente, imprime cuántas veces aparece. Tu primer array de conteo.

En una fraseCuenta cada dígito en un array de 10 posiciones e imprime solo los que aparecen, como digit:count en orden ascendente: un array de cubos fijos en vez de ordenar.

El problema

Entrada: Un entero no negativo (0 <= n <= 1000000000).

Salida: Una línea por dígito: dígito:veces, en orden ascendente.

Ejemplo:

EntradaSalida
1223331:1
2:2
3:3

Tu solución

main.cpp — tu solución
Entrada personalizada para «Ejecutar mi entrada»

La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.

¿Atascado? Pistas

Pista 1 — Array como contadores

int count[10] = {0}; y count[n % 10]++; por cada dígito.

Pista 2 — Imprime solo lo que existe

Recorre los diez dígitos e imprime solo si count[d] > 0.

Solución (¡inténtalo primero!) 
#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;
}

Es el patrón del counting sort y los histogramas. Compáralo con la versión de dos contadores.

Análisis profundo

Por qué funciona

Un array de conteo indexado por valor es la tabla hash más simple que existe: sin función hash, sin colisiones, O(1) por construcción.

El coste

O(n + 10) de tiempo y O(10) de espacio. Ese 10 es la razón por la que le gana a ordenar por un margen enorme.

Dónde falla

  • Indexar con un char usa su código ASCII (57 para '9'), no 9. Resta '0'.
  • Imprimir los diez cubos en vez de solo los que aparecieron falla la comparación exacta.

Siguiente paso

El mismo array con otra agregación: Sumar una matriz.

Dos cosas para recordar

  • Valor como índice es una tabla hash sin hash.
  • '9' - '0' == 9: ese desplazamiento ASCII es todo el truco.
🐞 Esta versión falla: ábrela y pruébala

Imprime los diez cubos en vez de solo los que aparecen

#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;
}