LeetCode - Easy - 258. Add Digits

向右看齐 2022-12-27 06:25 227阅读 0赞

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:

  1. Input: 38
  2. Output: 2
  3. Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2.
  4. 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

  1. import java.util.ArrayList;
  2. import java.util.List;
  3. public class AddDigits {
  4. public List<Integer> apart(int t1) {
  5. // int[] a = new int[32];//分别 存位数
  6. List<Integer> a = new ArrayList<>();
  7. int t2 = -1;
  8. for (int i = 0;; i++) {
  9. t2 = i == 0 ? t1 : (t2 - a.get(i - 1)) / 10;
  10. if (t2 == 0) {
  11. break;
  12. }
  13. a.add(t2 % 10);
  14. // System.out.print(a.get(i) + " ");
  15. }
  16. return a;
  17. }
  18. //通常法结合apart()使用
  19. public int addUp(List<Integer> fromList) {
  20. int s = 0;
  21. for (int i : fromList) {
  22. s += i;
  23. }
  24. while (s / 10 != 0) {
  25. s = addUp(apart(s));
  26. }
  27. return s;
  28. }
  29. //数学法
  30. public int addDigits(int num) {
  31. if (num == 0){
  32. return 0;
  33. }
  34. if (num % 9 == 0){
  35. return 9;
  36. }
  37. else {
  38. return num % 9;
  39. }
  40. }
  41. //最精简法
  42. public int addDigits2(int num) {
  43. return (num - 1) % 9 + 1;
  44. }
  45. }

Test

  1. import static org.junit.Assert.*;
  2. import org.junit.Test;
  3. public class AddDigitsTest {
  4. @Test
  5. public void test() {
  6. AddDigits ad = new AddDigits();
  7. assertEquals(2, ad.addUp(ad.apart(38)));
  8. assertEquals(2, ad.addDigits(38));
  9. assertEquals(2, ad.addDigits2(38));
  10. }
  11. }

发表评论

表情:
评论列表 (有 0 条评论,227人围观)

还没有评论,来说两句吧...

相关阅读