구글 입사문제라고 하는데...

1과 양의 정수 n 사이의 모든 정수에 대해 1이 나타나는 빈도함수를 f(n)이라고 하자. 예를 들어 f(13)=6이 된다 (<1>, <1>0, <1><1>, <1>2, <1>3). f(n)=n을 만족하는 첫번째 n은 1이다. 그러면 이 조건을 만족하는 두번째 n의 값은?

프로그램을 짜서 문제를 풀라는 건지 생각만으로 풀라는 건지 모르겠지만 요즘 유행하는 파이썬으로 한 번 짜보자면 다음과 같다.

#!/usr/bin/env python
import math

num_matches = 0
f = 0
n = 1
while num_matches <= 10:
	num_digits = int(math.log10(n)) + 1
	m = n
	for i in range(num_digits):
		a = m % 10
		if a == 1:
			f += 1
		m = (m - a) / 10
	if f == n:
		print "f(%d) = %d" % (n, f)
		num_matches += 1
	n += 1

그 결과는 아래와 같다.

f(1) = 1
f(199981) = 199981
f(199982) = 199982
f(199983) = 199983
f(199984) = 199984
f(199985) = 199985
f(199986) = 199986
f(199987) = 199987
f(199988) = 199988
f(199989) = 199989

정답은 199981이 되겠다.

역시 칠판에다 푸는 문제였다.

1. x자리수까지 답이 없었다.
2. x+1자리인 n=1999...999에 대해 f(n) < n이면
   1. x자리까지 답이 없었고 n=1999...999까지 f(n) < n이면 1000...000부터 1999...998까지는 f(n) >= n인 수가 있을 수 없다. 맨 첫숫자가 1이기 때문에 n의 증가분보다 f(n)의 증가분이 더 크고 만약 f(n)=n인 숫자가 그 사이에 있었다면 1999...999에서는 이미 f(n) >= n이 되어 있어야 한다.
   2. 1에 의해 x자리수인 m=999...999에 대해서는 f(m) < m이다.
   3. x+1자리인 y000...000부터 y999...999까지 (y는 2부터 9까지) 1의 개수는 y가 1이 아니기 때문에 f(m)과 동일하다.
   4. 따라서 x+1자리 마지막수인 9999...999까지 1의 수는 f(n)+8*f(m) < n+8*m = 9999...991이므로 f(9999...999) < 9999...999이다.
3. f(19) = 10+1*2 < 19
4. f(199) = 100+20*2 < 199
5. f(1999) = 1000+300*2 < 1999
6. f(19999) = 10000+4000*2 < 19999
7. f(199999) = 100000+50000*2 = 200000 > 199999
8. f(199991) = 200000-8 = 199992
9. f(199990) = 199990
10. f(199981) = 199990-9 = 199981 정답!
11. f(199980) = 199979