Frequency of Each Digit
Problem
Read an integer and print how many times each digit appears. Print only the digits that appear, from the smallest digit to the largest. Use the format digit: count. Ignore the minus sign.
Constraints
- -10^18 <= n <= 10^18
Examples
Input
112233
Output
1: 2 2: 2 3: 2
Solutions
A digit is always between 0 and 9, so an array of 10 counters is enough. The digit itself is the index of its counter. This idea is called a frequency array (counting sort).
/*
* Problem : Count how many times each digit appears.
* Input : One integer.
* Output : One line per digit that appears.
* Approach: Use an array of 10 counters, one for each digit.
* Time : O(d)
* Space : O(1)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
long number = Math.abs(new Scanner(System.in).nextLong());
// Step 1: Make an array with 10 counters. counts[3] will count the digit 3.
int[] counts = new int[10];
// Step 2: A do-while loop runs at least once, so the number 0 is counted too.
do {
// Step 3: Take the last digit. Example: 112233 % 10 = 3.
int digit = (int) (number % 10);
// Step 4: Add 1 to the counter of this digit. The digit is the index of the array.
counts[digit]++;
// Step 5: Remove the last digit. Example: 112233 / 10 = 11223.
number = number / 10;
} while (number > 0);
// Step 6: Print every digit that appeared at least once. Index 0 to 9 gives the smallest digit first.
for (int digit = 0; digit <= 9; digit++) {
if (counts[digit] > 0) {
System.out.println(digit + ": " + counts[digit]);
}
}
}
}
Hints (2)
- How many different digits exist?
- Can a digit be used as an array index?