LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 任意整数与它的各数位上数字的和对 9 同余

若 a ≡ b (mod m)，x ≡ y (mod m)，则 a + x ≡ b + y (mod m)
显然对任意自然数 n，a ≡ a * 10 ^ n (mod 9)
因此对 A = a[0] + a[1] * 10 + a[2] * 100 + ... + a[n] * 10 ^ n
其各数位上数字和 B =  a[0] + a[1] + a[2] + ... + a[n]
有 A ≡ B (mod 9)，即 (A - B) % 9 == 0

• 重复相加各数位的过程，最终得到的是一位数

(A - B) % 9 == 0
若 B < 9，则 B = A % 9
若 B == 9，则 A % 9 == 0

• 因此对任意正整数，若能被 9 整除，则各位相加即为 9，否则即为除以 9 的余数，对于 0 则结果为 0

class Solution {
 public:
  int addDigits(int num) {
    if (!num) {
      return 0;
    }
    int res = num % 9;
    if (!res) {
      return 9;
    }
    return res;
  }
};