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?

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

Hint:

- A naive implementation of the above process is trivial. Could you come up with other methods?
- What are all the possible results?
- How do they occur, periodically or randomly?
- You may find this Wikipedia article useful

**Brute-force solution:**

public class Solution { public int addDigits(int num) { if (num < 10) { return num; } int result = num; while (result >= 10) { // Get each didgit of the number int digit = 0; while (result > 0) { digit += result % 10; result /= 10; } result = digit; } return result; } }

**O(1) time solution:**

Let's enumerate numbers from 1 - 19,

in out

1 1

2 2

3 3

...

9 9

10 1

11 2

12 3

13 4

14 5

...

19 1

20 2

21 3

...

28 1

29 2

30 3

...

So the result = (n - 1) % 9 + 1

**Code (Java):**

public class Solution { public int addDigits(int num) { if (num <= 0) { return 0; } return (num - 1) % 9 + 1; } }

## No comments:

## Post a Comment