LeetCode - Easy - 258. Add Digits-蒲公英云

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:

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));
    }
}