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