问题如下：

给一个非负整数 num，反复添加所有的数字，直到结果只有一个数字。

例如:

设定 num = 38，过程就像： 3 + 8 = 11, 1 + 1 = 2。由于 2 只有1个数字，所以返回它。

进阶:

你可以不用任何的循环或者递归算法，在 O(1) 的时间内解决这个问题么？

初始的想法：

开始只看到了进阶，要求使用O(1)的时间复杂度，因此我想了一下，既然是int型变量，那么它的范围是-32768~32767，因此最高一共有5位数，所以O(1)算法可以直接使用五个int型变量存储起来然后相加，最多连续相加两次即可得到个位数，因此初始写的代码如下：

class Solution {

public:

    int addDigits(int num) {

        int a1,a2,a3,a4,a5,sum = 0;//将数据拆开后相加

        a1 = num%10;

        num /= 10;

        a2 = num%10;

        num /= 10;

        a3 = num%10;

        num /= 10;

        a4 = num%10;

        num /= 10;

        a5 = num%10;

        sum = a1+a2+a3+a4+a5;

        a1 = sum%10;//此时最多还有两位数有实际意义，再相加一次

        sum /= 10;

        a2 = sum%10;

        sum = a1+a2;

        a1 = sum%10;//此时最多还有两位数有实际意义，再相加一次，必然得到个位数最终结果

        sum /= 10;

        a2 = sum%10;

        sum = a1+a2;

        return sum;

    }

};

但是。。。。。。我还是Too Young Too Simple。。。

谁TM知道这个int竟然是超过五位数的啊！！！

分析错误：

于是乎我就查了一下资料。。。看看int究竟是怎么个一回事。。。。。

int型长度到底是几个字节?(http://blog.sina.com.cn/s/blog_865e6dd50102vmqr.html)

在一些没有操作系统的嵌入式计算机系统上，int的长度与处理器字长一致；有操作系统时，操作系统的字长与处理器的字长不一定一致，此时编译器根据操作系统的字长来定义int字长：“比如你在64位机器上运行DOS16系统，那么所有for dos16的C/C++编译器中int都是16位的；在64位机器上运行win32系统，那么所有for win32的C/C++编译器中int都是32位的”。（CPU的“字长”是指其一条指令/一次运算可以处理的数据的最大宽度。

所以说int类型并不一定只有4位或者两位。。。。因此要考虑到数字特别大的情况。。。。。。。。

改正错误：

因此我还是用循环函数吧。。。。。。代码如下

class Solution {

public:

    int addDigits(int num) {

        int i,sum = 0;

        while(1)

        {

            while(num != 0)

            {

                sum += num%10;

                num /= 10;

            }

            if(sum >= 10)

            {

                num = sum;

                sum = 0;

            }

            else

                break;

        }

        return sum;

    }

};

这次问题成功解决了。

问题：

那么究竟用什么方法才能达到O(1)的时间复杂度呢？这个问题在我详细的学习算法后再进行解答。

巴特西

LeetCode(258.各位相加)的思路及解决过程