LeetCode - Easy - 258. Add Digits
Topic
Math
Description
https://leetcode.com/problems/add-digits/
Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
Example:
Input: 38
Output: 2
Explanation: 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?
Analysis
1
按照正常的套路完成算法
2
用数学分析它的算法
I’ll try to explain the math behind this:
First you should understand:
10^k % 9 = 1
**a*10^k % 9 = a % 9 **
Then let’s use an example to help explain.
Say a number x = 23456
x = 2 * 10000 + 3 * 1000 + 4 * 100 + 5 * 10 + 6
2 * 10000 % 9 = 2 % 9
3 * 1000 % 9 = 3 % 9
4 * 100 % 9 = 4 % 9
5 * 10 % 9 = 5 % 9
Then x % 9 = ( 2 + 3 + 4 + 5 + 6) % 9, note that x = 2 * 10000 + 3 * 1000 + 4 * 100 + 5 * 10 + 6
So we have 23456 % 9 = (2 + 3 + 4 + 5 + 6) % 9 [1]
Submission
import java.util.ArrayList;
import java.util.List;
public class AddDigits {
public List<Integer> apart(int t1) {
// int[] a = new int[32];//分别 存位数
List<Integer> a = new ArrayList<>();
int t2 = -1;
for (int i = 0;; i++) {
t2 = i == 0 ? t1 : (t2 - a.get(i - 1)) / 10;
if (t2 == 0) {
break;
}
a.add(t2 % 10);
// System.out.print(a.get(i) + " ");
}
return a;
}
//通常法结合apart()使用
public int addUp(List<Integer> fromList) {
int s = 0;
for (int i : fromList) {
s += i;
}
while (s / 10 != 0) {
s = addUp(apart(s));
}
return s;
}
//数学法
public int addDigits(int num) {
if (num == 0){
return 0;
}
if (num % 9 == 0){
return 9;
}
else {
return num % 9;
}
}
//最精简法
public int addDigits2(int num) {
return (num - 1) % 9 + 1;
}
}
Test
import static org.junit.Assert.*;
import org.junit.Test;
public class AddDigitsTest {
@Test
public void test() {
AddDigits ad = new AddDigits();
assertEquals(2, ad.addUp(ad.apart(38)));
assertEquals(2, ad.addDigits(38));
assertEquals(2, ad.addDigits2(38));
}
}
还没有评论,来说两句吧...