ReZero's Utopia.

# Leet-Code

Word count: 850Reading time: 4 min
2020/08/14 Share

Since 10^{i}$\equiv 1（mod 9) ,then => (a_{i}$ * 10^{i}$+ a_{i-1}$ * 10^{i-1}$+ …) mod 9 = (a_{i}$ * 10^{i}$mod 9 + a_{i-1}$ * 10^{i-1}$mod 9 + …) mod 9 = (a_{i}$ + a_{i-1}\$ + …) mod 9

https://en.wikipedia.org/wiki/Digital_root#Congruence_formula

For base b (decimal case b = 10), the digit root of an integer is:

• dr(n) = 0 if n == 0
• dr(n) = (b-1) if n != 0 and n % (b-1) == 0
• dr(n) = n mod (b-1) if n % (b-1) != 0

or

• dr(n) = 1 + (n - 1) % 9

Note here, when n = 0, since (n - 1) % 9 = -1, the return value is zero (correct).

From the formula, we can find that the result of this problem is immanently periodic, with period (b-1).

Output sequence for decimals (b = 10):

Henceforth, we can write the following code, whose time and space complexities are both O(1).

Input: 00000010100101000001111010011100

Output: 00111001011110000010100101000000

Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

https://leetcode.com/problems/reverse-bits/discuss/54741/O(1)-bit-operation-C%2B%2B-solution-(8ms)

Explanation:
// 12345678
// 56781234
// 78563412
// 87654321

Author：ReZero

CATALOG