Given a non-negative integer number, 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.
Submit your solution at: https://leetcode.com/problems/add-digits/
Naive Solution – Simulation
We simulate how it works by adding all digits until the sum is less than 10.
class Solution {
public:
int addDigits(int num) {
while (num > 0) {
int cnt = 0;
while (num > 0) {
cnt += num % 10; // sum up each digit
num /= 10;
}
if (cnt < 10) return cnt;
num = cnt; // make sum the new number
}
return 0;
}
};
1101 / 1101 test cases passed. Runtime: 12 ms
O(1) Math Solution
Based on the Wiki Page – Digit Root, we know that (1), the multiples of 9 has a digit root = 9, for example, 9, 18 (1+8), 27 (2+9), 189 (1+8+9=18=1+8) etc. and any other non-negative integers have a digit root which is 1 + floor((n – 1) % 9). For example, 11 is the second number after 9, so it has a digit root equals to 1 + ((11 – 1) % 9) = 2.
82 is the first number after multiples of 9, so the digit root = 1 + ((82 – 1) % 9) = 1.
class Solution {
public:
int addDigits(int num) {
return 1 + ((num - 1) % 9);
}
};
Runtime: 8ms.
–EOF (The Ultimate Computing & Technology Blog) —
262 wordsLast Post: Microsoft DOS Mobile 1.0 on Nokia Lumia 635
Next Post: The 'trapped' notice
Solution in java :
public static void main(String[] args) {
long start = System.nanoTime();
System.out.println(oneInt(98654));
long end = System.nanoTime();
System.out.print(end – start);
System.out.println(” nano second”);
}
public static int oneInt(int integer,int size){
if(size==1) return integer;
String temp = integer+””;
integer=0;
for(char t : temp.toCharArray()) integer+= t – ‘0’;
return oneInt(integer, String.valueOf(integer).length());
}
public static int oneInt(int integer){
return oneInt(integer,String.valueOf(integer).length());
}
result:
5
251033 nano second
BUILD SUCCESSFUL (total time: 0 seconds)