🔗 Full Problem 1019

Jimin has a book with a total of $N$ pages. The first page is page 1, and the last page is page $N$. Let's find out how many times each digit appears across all the page numbers.

The first line gives $N$. $N$ is a natural number less than or equal to $1,000,000,000$.

On the first line, print how many times 0 appears in total, how many times 1 appears, ..., and how many times 9 appears, separated by spaces.

• Input

TC
11

• Output

TC
1 4 1 1 1 1 1 1 1 1

The problem is clear and intuitive. When listing pages from page 1 to page $N$, this problem asks us to count how many times each digit was used.

To write the number 165, the digits $[ 1, 5, 6 ]$ are used. In this way, we need to count how many times each digit from 0 was used to write out every number from 1 to the given number, and print them in ascending order starting from 0.

In other words, if $N = 5$, the pages listed are $[ 1, 2, 3, 4, 5 ]$. The table below shows how many times each digit was used.

Listing from 1 to 5, each digit is used exactly once, so it can be shown as above. So what about the example value 11?

The numbers listed are $[ 1, 2, 3, \dots, 10, 11 ]$.

From 1 to 9, each digit is used once each; 10 uses 1 and 0; and 11 uses 1 twice.

Each digit was used as many times as shown in the table above. To help with understanding, let's also try $N = 13$.

$12 = [ 1, 2 ]$, $13 = [ 1, 3 ]$. Since 1 to 13 also includes 11, we can just add the values for 12 and 13 to the result for 11.

I think this is enough for you to understand what the algorithm needs to do.

Honestly, if you approach this brute-force, it isn't that hard a problem. Just loop through each number, break it into its digits, and add each one to the corresponding count. Unfortunately, though, the maximum value of $N$ is close to one billion (luckily, it doesn't exceed the max value of int). That means a brute-force approach won't cut it.

So we need to find some pattern hidden somewhere and design a general formula. In situations like this, listing things out one by one usually reveals it.

I went a little past 20 to lay out the digit usage counts and look for patterns. Some kind of pattern does seem to appear.

1. 0 increases by 1 with every multiple of 10.
2. Each digit in the ones place increases by 1 for the corresponding number, and its final value is equal to the tens digit + 1.
3. The tens digit increases the corresponding number by 1.

Just staring at it, it can be a bit hard to spot the pattern. The answer lies in the range *0 through *9. For example, let's list out 10 through 29. Rather than starting from 1, let's assume we're computing the algorithm based on an arbitrary range $A$ through $B$.

Looking closely at the numbers in the table above, you can see that each ones digit is used exactly once per row.

Now the pattern starts to stand out a bit. In a range of the form *0 through *9, such as 20 through 39, every digit in the ones place is used the same number of times. Since there are two such ranges here — 10 to 19 and 20 to 29 — every digit is used twice, once per range.

If we call the starting page $n$ and the ending page $N$, this rule can be written as a general formula as follows.

$$(N \div 10) - (n \div 10) + 1 = \text{count of each individual digit used in the ones place}$$

Therefore, we can see that in the range 10 to 29, every digit is used exactly twice.

The problem is that the formula above only applies to the ones place. Pages can have up to 10 digits. In other words, we need a general formula that applies universally.

Conversely, let's take a close look at the tens digit. 1 is used 10 times. If the range were 100 to 199, 1 would be used 100 times, and if the range were 1000 to 1999, 1 would be used 1000 times.

For convenience, let's define a "unit range" as a range of the form $n0* \sim n9*$, like 10 to 19, 100 to 199, or 1000 to 1999. In that case, the count of times $n$ is used in that range can be defined as follows.

$$((N \div 10) - (n \div 10) + 1) \times \text{p} = \text{count for each individual digit}$$

• $n$: starting value of the range
• $N$: ending value of the range
• $p$: place value

Now, as long as we have a matching range, we can find the count of a given digit — but this is still limited.

First, in this algorithm, the starting value is always fixed at 1. The ending value $N$ also doesn't necessarily come in as a unit range like 199. If $N = 35$, we need to apply the algorithm to the range 1 to 35. Unless the range happens to be something like 10 to 39, the general formula above doesn't directly apply to a range with a completely different shape.

The solution is simple. Just like adjusting for windage by adding and subtracting corrections, we add and subtract values to bring the range into the right shape.

In the range 1 to 35, for the number 1: the nearest value greater than 1 that includes a 0 is 10. So we increase the starting value up to 10, counting each number as we go. Since we count from 1 through 9, this can be shown in a table as follows.

For 35, the nearest value less than 35 that includes a 9 is 29. Similarly, we decrease the ending value down to 29, counting each number as we go. Since we count from 35 down to 30, this can be shown in a table as follows.

In other words, the initial value is the array with these correction values already added, and subsequent calculations are accumulated on top of this initial value.

When $N = 1999$ and $n = 1000$, the count of digits used in the ones place is computed as follows.

$$((1999 / 10) - (1000 / 10) + 1) \times 1 = 100$$

Each digit is used 100 times in the ones place. What about the tens place?

Dividing $N$ and $n$ each by 10 gives us the range for the tens place. We apply the divided values to the general formula above.

$$((199 / 10) - (100 / 10) + 1) \times 10 = 100$$

For the hundreds place, we compute by dividing $N$ and $n$ each by 100.

$$((19 / 10) - (10 / 10) + 1) \times 100 = 100$$

For the thousands place, we compute by dividing $N$ and $n$ each by 1000. But since $N = n = 1$, only the digit 1 gets 1000 uses.

So the range 1000 to 1999 is computed as shown above.

For a full understanding, let's use these concepts to compute the algorithm for $N = 4153$.

Since $N = 4153$, the range is 1 to 4153.

We move up to 10, the nearest number greater than 1 whose ones digit is 0, counting each number we pass along the way separately.

We move from 1 through 9 to reach 10, so we count 1 through 9 separately.

We move down to 4149, the nearest number less than 4153 whose ones digit is 9, counting each number we pass along the way separately.

We move from 4153 down to 4149, so we count these separately.

Now that we have a range 10 to 4149 that the general formula can be applied to, let's apply it.

$$((4149 / 10) - (10 / 10) + 1) \times 1 = 414 - 1 + 1 = 414$$

To compute the next digit place, we divide the ones-place general formula's range values, 4149 and 10, each by 10.

The range for the tens place becomes $1 \sim 414$. Similarly, we adjust the range for the general formula to apply. Since this is the tens place, note that a move from 1 to 2 actually corresponds to a move from 10 to 20.

Now that we have a range 10 to 409 that the general formula can be applied to, let's apply it.

$$((409 / 10) - (10 / 10) + 1) \times 10 = (40 - 1 + 1) \times 10 = 400$$

To compute the next digit place, we divide the tens-place general formula's range values, 409 and 10, each by 10.

The range for the hundreds place becomes $1 \sim 40$. The rest of the process is the same as for the tens place.

Now that we have a range 10 to 39 that the general formula can be applied to, let's apply it.

$$((39 / 10) - (10 / 10) + 1) \times 100 = (3 - 1 + 1) \times 100 = 300$$

To compute the next digit place, we divide the hundreds-place general formula's range values, 39 and 10, each by 10.

The range for the thousands place becomes $1 \sim 3$.

There's one issue here: for the final range, the smallest value whose ones digit is 9 would be -9. Since negative numbers can't occur, no further general-formula computation is possible, so we just add these values individually.

Let's organize everything computed at each stage into a table of grand totals.

The algorithm's result for the range 1 to 4153 is as shown above.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

/**
 * 백준 전체 1019 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/28/a1019">1019 풀이</a>
 * @since 2021.06.28 Mon 12:28:50
 */
public class Main
{
	// 숫자 카운트 배열
	private static final int[] COUNTER = new int[10];
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 마지막 페이지
		int N = Integer.parseInt(reader.readLine());
		
		solve(N);
		
		StringBuilder builder = new StringBuilder();
		
		for (int item : COUNTER)
		{
			builder.append(item).append(" ");
		}
		
		writer.write(builder.toString().trim());
		writer.newLine();
		writer.flush();
		
		reader.close();
		writer.close();
	}
	
	/**
	 * 알고리즘 동작 함수
	 *
	 * @param num: [int] 마지막 페이지
	 */
	private static void solve(int num)
	{
		// 시작 페이지
		int start = 1;
		
		// 자릿수
		int digit = 1;
		
		while (start <= num)
		{
			// 1의 자리가 9가 될 때까지 마지막 페이지를 1씩 감소함
			while (num % 10 != 9 && start <= num)
			{
				// 감소한 페이지 별도 카운팅
				count(num, digit);
				
				num--;
			}
			
			// 마지막 페이지가 시작 페이지보다 작을 경우
			if (num < start)
			{
				// 이를 처리하지 않으면 num < 9일 경우 무한루프를 탐
				break;
			}
			
			// 1의 자리가 0이 될 때까지 시작 페이지를 1씩 증가함
			while (start % 10 != 0 && start <= num)
			{
				// 증가한 페이지 별도 카운팅
				count(start, digit);
				
				start++;
			}
			
			start /= 10;
			num /= 10;
			
			for (int i = 0; i < 10; i++)
			{
				COUNTER[i] += (num - start + 1) * digit;
			}
			
			// 자릿수 증가
			digit *= 10;
		}
	}
	
	/**
	 * 카운트 함수
	 *
	 * @param num: [int] 대상 숫자
	 * @param digit: [int] 자릿수
	 */
	private static void count(int num, int digit)
	{
		while (num > 0)
		{
			COUNTER[num % 10] += digit;
			num /= 10;
		}
	}
}

When $N = 4153$, during the process of adjusting the range, numbers like 4153 and 4152 need to be counted individually.

JAVA
/**
 * 카운트 함수
 *
 * @param num: [int] 대상 숫자
 * @param digit: [int] 자릿수
 */
private static void count(int num, int digit)
{
	while (num > 0)
	{
		counter[num % 10] += digit;
		num /= 10;
	}
}

The logic isn't difficult. Since 4152 consists of the digits $[ 4, 1, 5, 2 ]$, all you need to do is add the digit place value (1 for ones, 10 for tens, and so on) to the count for each corresponding digit.

The ones digit can be found with $4152 \,\,\, \% \,\,\, 10 = 2$. The tens digit can be found by dividing 4152 by 10 once and repeating the same operation. The hundreds place, thousands place, and so on can be computed by repeating this as many times as there are digits.

JAVA
/**
 * 알고리즘 동작 함수
 *
 * @param num: [int] 마지막 페이지
 */
private static void solve(int num)
{
	// 시작 페이지
	int start = 1;
	
	// 자릿수
	int digit = 1;
	
	while (start <= num)
	{
		// 1의 자리가 9가 될 때까지 마지막 페이지를 1씩 감소함
		while (num % 10 != 9 && start <= num)
		{
			// 감소한 페이지 별도 카운팅
			count(num, digit);
			
			num--;
		}
		
		// 마지막 페이지가 시작 페이지보다 작을 경우
		if (num < start)
		{
			// 이를 처리하지 않으면 num < 9일 경우 무한루프를 탐
			break;
		}
		
		// 1의 자리가 0이 될 때까지 시작 페이지를 1씩 증가함
		while (start % 10 != 0 && start <= num)
		{
			// 증가한 페이지 별도 카운팅
			count(start, digit);
			
			start++;
		}
		
		start /= 10;
		num /= 10;
		
		for (int i = 0; i < 10; i++)
		{
			counter[i] += (num - start + 1) * digit;
		}
		
		// 자릿수 증가
		digit *= 10;
	}
}

The starting page is always fixed at 1. We repeat until the starting page exceeds the ending page.

In the first while loop, we decrease the ending page by 1 at a time, adjusting it into a range ending in 9. There's a condition in the middle of it — without this handling, if num is smaller than 9, start would never exceed num during the process, causing an infinite loop.

The second while loop increases page 1 by 1 at a time, adjusting it into a range starting at 0. All adjusted values are counted separately through the count method.

Once the range has been adjusted through this process, all that's left is to apply the formula mentioned above and repeat it.

• Mathematics