// Source : https://leetcode.com/problems/add-digits/

// Author : Timothy Lim, Hao Chen

// Date : 2015-10-1

/**********************************************************************************

* 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.

*

* Follow up:

* Could you do it without any loop/recursion in O(1) runtime?

*

**********************************************************************************/

class Solution {

public:

int addDigits(int num) {

switch(random()%5+1){

case 1: return addDigits01(num);

case 2: return addDigits02(num);

case 3: return addDigits03(num);

case 4: return addDigits04(num);

default: return addDigits05(num);

}

}

//regualr way

int addDigits01(int num) {

while(num > 9) {

int sum;

for(sum=0; num > 0; sum += num%10 , num/=10);

num = sum;

}

return num;

}

//This solution looks is very tricky, but acutally it is easy to understand.

//it just keep adding the last digital until the num < 10

int addDigits02(int num) {

while(num > 9) {

num = num / 10 + num % 10;

}

return num;

}

// Let's observe the pattern

// 1 1

// 2 2

// ... ...

// 8 8

// 9 9

// 10 1

// 11 2

// 12 3

// ... ...

// 17 8

// 18 9

// 19 1

// 20 2

// ... ...

// It looks most of number just simply %9 is the answer,

// but there are some edge cases.

// 9%9=0 but we need 9.

// 18%9=0 but we need 9

// so we can find the solution is:

// 1) num <=9, return num

// 2) num > 9, reutrn num%9 if num%9>0

// return 9 if num%9 ==0

int addDigits03(int num) {

return num >9 ? ((num %9)==0 ? 9:num%9) : num;

}

//But actually, we can use (num-1)%9 + 1 to make all cases right.

int addDigits04(int num){

return (num - 1) % 9 + 1;

}

//This solution is similar with pervious solution.

int addDigits05(int num){

return num - 9 * ((num - 1)/9);

}

};