据说是google的面试题,看谁的快.pdf

据说是据说是 google 的面试题 看谁的快的面试题 看谁的快 Consider a function which for a given whole number n returns the number of ones required when writing out all numbers between 0 and n For example f 13 6 Notice that f 1 1 What is the next largest n such that f n n 翻译过来大体是这样 有一个整数 n 写一个函数 f n 返回 0 到 n 之间出现的 1 的个数 比如 f 13 6 现在 f 1 1 问此后最大的 f n n 的 n 是什么 f 13 6 是 因为 1 2 3 4 5 6 7 8 9 10 11 12 13 中 1 的个数 正好是 6 我写了一个 用了不到一秒的时间 结果如下 QUOTE 1 199981 199982 199983 199984 199985 199986 199987 199988 199989 199990 200000 200001 1599981 1599982 1599983 1599984 1599985 1599986 1599987 1599988 1599989 1599990 2600000 2600001 13199998 35000000 35000001 35199981 35199982 35199983 35199984 35199985 35199986 35199987 35199988 35199989 35199990 35200000 35200001 117463825 500000000 500000001 500199981 500199982 500199983 500199984 500199985 500199986 500199987 500199988 500199989 500199990 500200000 500200001 501599981 501599982 501599983 501599984 501599985 501599986 501599987 501599988 501599989 501599990 502600000 502600001 513199998 535000000 535000001 535199981 535199982 535199983 535199984 535199985 535199986 535199987 535199988 535199989 535199990 535200000 535200001 1111111110 如果能看懂上面的证明 那下面的这个程序就很自然了 CODE Copy to clipboard long long f long long n int k long long e m n r if n 10 k e 10 m 10 r n m e if m 1 return e 10 k r 1 f r else return e 10 k m e f r int digit num long long n int k for k 0 n 0 k n 10 return k int