今天电面考了Happy Number, 挂了, 求指导 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

今天电面考了Happy Number, 挂了, 求指导

今天电面考了Happy Number, 挂了, 求指导# JobHunting - 待字闺中

m*p2014-02-20 08:02

1 楼

Happy Number 定义为 (只考虑正整数):
1是Happy number,
各个数字的平方和为happy number, 那么这个数字是happy number
例子: 13 -> 1^2+3^2 -> 10 -> 1^2+0^2 -> 1
这样13和10都是happy number
我的思路是: 如果计算出1，返回true，如果算出了以前出现过的数，返回false(因
为会形成一个循环，这样永远到不了1)
看网上的思路大体就是这样，可是今天面的三哥非要问：
为什么不能有第三种情况，就是一直不出现重复数字，还一直无法得到1(不断增长下去
)？
我也给不出严格证明，三哥最后给个方案，如果下一个int数字overflow的话，就返回
false
可是这完全多此一举，因为不会有这种情况的，请问如何能给出严格证明？

l*62014-02-20 08:02

2 楼

Suppose the number gets to n digits, next number is less than
9^2 * n = 81 * n
this is strictly less than the number itself, which is greater than
10^(n - 1)
when n gets greater or equal than 4
so the number will decrease after operation
no possible to overflow
laoyin doesn't know math

r*l2014-02-20 08:02

3 楼

CS的面试题不要过多地从数学角度想。毕竟出这个题是考查你coding方面的能力，而不
是你数学有多强。他的意思应该就是看你的程序能否cover各种情况而已。
我以前碰到过一个面试题让不用sqrt函数计算平方根。我说用泰勒级数来算，他不愿意
。扯了半天发现其实他想要的答案是binary search而已。

K*g2014-02-20 08:02

4 楼

考虑INT_MAX，共10位，平方和小于10*（9*9）=810。
之后的平方和都小于810，所以不会一直增长，更不可能溢出。

【在 m***p 的大作中提到】

: Happy Number 定义为 (只考虑正整数):
: 1是Happy number,
: 各个数字的平方和为happy number, 那么这个数字是happy number
: 例子: 13 -> 1^2+3^2 -> 10 -> 1^2+0^2 -> 1
: 这样13和10都是happy number
: 我的思路是: 如果计算出1，返回true，如果算出了以前出现过的数，返回false(因
: 为会形成一个循环，这样永远到不了1)
: 看网上的思路大体就是这样，可是今天面的三哥非要问：
: 为什么不能有第三种情况，就是一直不出现重复数字，还一直无法得到1(不断增长下去
: )？

s*d2014-02-20 08:02

5 楼

可以证明啊
9*9=81
9..9 设有N个9，当N>2，总有 81*N < 10^N
所以是有限的，不可能不断增长

w*e2014-02-20 08:02

6 楼

http://en.wikipedia.org/wiki/Happy_number
Sequence behavior 给出了证明
so any number over 1000 gets smaller under this process and in particular
becomes a number with strictly fewer digits. Once we are under 1000, the
number for which the sum of squares of digits is largest is 999, and the
result is 3 times 81, that is, 243.