Add Digits

  |   0 评论   |   403 浏览

    Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
    For example:
    Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

    要求:Could you do it without any loop/recursion in O(1) runtime?
    思考2min


    感觉这类题还是多看多积累经验得好。迭代实现是基本没问题的了,但 O(1)复杂度,就是要一次计算出来。得推理出规律。。

    推理:

    整数 A 表示成 100a+10b+c,然后=(100a+10b+c)%9=(a+99a+b+9b+c)%9=(a+b+c)%9

    然后就自然得得到解。。return (num - 1) % 9 + 1;

    评论

    发表评论

    validate