[剑指Offer] Day 31: Mathematics

Authored by Tony Feng

Created on May 11th, 2022

Last Modified on May 11th, 2022

Task 1 - Q14,II. 剪绳子 II

Question

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。其中，2 <= n <= 58。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution: # Quick Power
    def cuttingRope(self, n: int) -> int:
        if n <= 3: return n - 1
        a, b = n // 3 - 1, n % 3
        x, p, rem = 3, 1000000007, 1

        while a > 0:
            if a % 2 == 1:
                rem = (rem * x) % p

            x = (x ** 2) % p
            a = a // 2

        if b == 0: 
            rem = (rem * 3) % p         # 3^(a+1) % p
        elif b == 1: 
            rem = (rem * 2 * 2) % p     # 3^a * 4 % p
        else: 
            rem = (rem * 3 * 2) % p     # 3^(a+1) * 2 % p

        return rem

Explanation

Mathematical Theory
- When the length sub-line is 3, the product reaches maximum. (Q14,I. 剪绳子 I)
- Remainder Operation (x < p, according to the question) $$ x^{a} \odot p = [(x^{a-1} \odot p)(x \odot p)] \odot p=[(x^{a-1} \odot p) x] \odot p $$
- Exponentiation by Squaring
  - a is even: $ x^{a} \odot p = (x^{2} \odot p)^{a // 2} \odot p$
  - a is odd : $ x^{a} \odot p= {[(x \odot p)(x^{a-1} \odot p)] \odot p=[x(x^{2} \odot p)^{a // 2}] \odot p} $
Time Complexity: O(log(N))
Space Complexity: O(1)

Task 2 - Q43. 1～n 整数中 1 出现的次数

Question

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def countDigitOne(self, n: int) -> int:
        digit, res = 1, 0
        high, cur, low = n // 10, n % 10, 0

        while high != 0 or cur != 0: # Check if digit is over the highest place
            if cur == 0: 
                res += high * digit
            elif cur == 1: 
                res += high * digit + low + 1
            else: 
                res += (high + 1) * digit
                
            low += cur * digit  # low for the next round
            cur = high % 10     # cur for the next round
            high //= 10         # high for the next round
            digit *= 10         # digit for the next round
        return res

Explanation

Time Complexity: O(log(N))
Space Complexity: O(1)

Task 3 - Q44. 数字序列中某一位的数字

Question

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
    def findNthDigit(self, n: int) -> int:
        if n < 10: return n 

        '''
        The index begins from 0 and the first number is 0, so we can start from 1. 
        1 ~ 9:          9 numbers
        10 ~ 99:        9 * 10 numbers
        100 ~ 999:      9 * 100 numbers
        1000 ~ 9999:    9 * 1000 numbers
        '''
        digit, start, cnt = 1, 1, 9
        while n > cnt:
            start *= 10
            digit += 1
            cnt += 9 * start * digit   

        cnt -= 9 * start * digit    # Find the lower bound
        rem  = (n - cnt) % digit    # Find which place the single number is in
        num = start - 1 + (n - cnt) // digit if rem == 0 else start + (n - cnt) // digit    # Ceiling 向上取整

        return int(str(num)[rem-1])

Solution 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def findNthDigit(self, n: int) -> int:
        digit, start, count = 1, 1, 9
        while n > count: 
            n -= count
            start *= 10
            digit += 1
            count = 9 * start * digit

        num = start + (n - 1) // digit 
        return int(str(num)[(n - 1) % digit]) 

Explanation

Time Complexity: O(log(N))
Space Complexity: O(log(N))