구글 입사 문제 1부터 10000까지 8은 몇 개?

아닌 밤에 갑자기 어느 게시판에서 봐서 함 풀어 봤습니다.

a(n)이 n자리수까지 8의 개수라고 하면, 우선 a(0) = 0으로 두고 (당연히 0자리수는 아무것도 없으니)

a(n) = a(n-1)*10 + Power(10, n-1)

즉, 

a(1) = 1  (0부터 9까지 8의 개수는 1, 10을 넣어도 마찬가지)

a(2) = 1 * 10 + Power(10, 2-1) = 20

a(3) = 20 * 10 + Power(10, 3-1) = 300

a(4) = 300 * 10 + Power(10, 4-1) = 4000

따라서, 1부터 10000까지의 8의 개수는 4000개!

왜냐하면, 이전 자리의 덧샘이 10번 반복되고, 이전 자리에 없었던 자리에 8의 자리가 10배씩 증가한다.

이전 자리에 없었던 자리에 8의 자리라함은, 1부터 10에는 없었던 80-89 이렇게 10개 늘어나고,

1부터 100에 없었던 800-899 이렇게 100개 늘어나기 시작한다.  

이때 맨 앞에 8이하는 이미 셈에 들어 갔기 때문에, 88 등을 고민 할 필요가 없다.

풀고나서 검색해보니, 더 쉽게 찾으신 분도 있군요.

0000부터 시작해서 9999로 모든 숫자 개수는 4 * 10000 개 (0이 아니라 0000처럼 세는 것에 주의)

8은 1/10의 비율로 존재하니까 4000 개라고 푸신 분이 있네요.