2021-08-27: the normal odometer will display natural numbers in turn to indicate mileage, Kyrgyzstan

2021-08-27： The normal odometer will display natural numbers in turn, indicating mileage , An auspicious odometer will ignore 4 And jump to the next one without 4 Number of numbers . normal ：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 X. auspicious ：1 2 3 5 6 7 8 9 10 11 12 13 15 16 17 ... 38 39 50 51 52 53 55. Give a lucky odometer number num( Of course, this number does not contain 4). Return the actual mileage represented by this number .

Fuda answer 2021-08-27：

The essence of this problem is a 9 The base number is converted to 10 Binary number .

0-3 unchanged .5-9 become 4-8.

such as 39, First become 38, then 3*9+8=35.35 Is the value you need to return .

Time complexity ：O(lgN).

Spatial complexity ：O(1).

The code to use golang To write . The code is as follows ：

package main

import "fmt"

func main() {
    ret := notContains4Nums1(39)
    fmt.Println(ret)

    ret = notContains4Nums2(39)
    fmt.Println(ret)

    ret = notContains4Nums3(39)
    fmt.Println(ret)
}

// num There must be no 4 This number 
func notContains4Nums1(num int) int {
    count := 0
    for i := 1; i <= num; i++ {
        if isNot4(i) {
            count++
        }
    }
    return count
}

func isNot4(num int) bool {
    for num != 0 {
        if num%10 == 4 {
            return false
        }
        num /= 10
    }
    return true
}

// arr[1] :  Than 1 The number of digits is still small 1 position , There are several numbers ( Numbers can contain 0 But it cannot contain 4)？0 individual 
// arr[2] :  Than 2 The number of digits is still small 1 position , There are several numbers ( Numbers can contain 0 But it cannot contain 4)？9 individual 
// 1 -> 0 1 2 3 - 5 6 7 8 9 = 9
// arr[3] : Than 3 The number of digits is still small 1 position , There are several numbers ( Numbers can contain 0 But it cannot contain 4)？81 individual 
// 1 : 0 (0 1 2 3 - 5 6 7 8 9) = 9
// 2 :
// 1 (0 1 2 3 - 5 6 7 8 9) = 9
// 2 (0 1 2 3 - 5 6 7 8 9) = 9
// 3 (0 1 2 3 - 5 6 7 8 9) = 9
// 5 (0 1 2 3 - 5 6 7 8 9) = 9
// ...
// 9 (0 1 2 3 - 5 6 7 8 9) = 9
var arr []int = []int{0, 1, 9, 81, 729, 6561, 59049, 531441, 4782969, 43046721, 387420489,
    3486784401, 31381059609, 282429536481, 2541865828329, 22876792454961, 205891132094649,
    1853020188851841, 16677181699666569, 150094635296999121, 1350851717672992089}

// num There must be no 4 This number 
func notContains4Nums2(num int) int {
    if num <= 0 {
        return 0
    }
    // num The decimal digits of ,len
    len2 := decimalLength(num)
    // 35621
    // 10000
    offset := offset(len2)

    //  First digit 
    first := num / offset
    return arr[len2] - 1 + (first-twoSelectOne(first < 4, 1, 2))*arr[len2] + process(num%offset, offset/10, len2-1)
}

// num Before , There is a beginning ！
//  It's about 0 Under the circumstances ,num It's the number 
// num 76217
// 10000
// 6217
// 1000
// len
func process(num int, offset int, len2 int) int {
    if len2 == 0 {
        return 1
    }
    first := num / offset
    return twoSelectOne(first < 4, first, (first-1))*arr[len2] + process(num%offset, offset/10, len2-1)
}

// num The decimal digits of 
// num = 7653210
// 7
func decimalLength(num int) int {
    len2 := 0
    for num != 0 {
        len2++
        num /= 10
    }
    return len2
}

// len = 6
// 100000
// len = 4
// 1000
// 3452168
// 1000000
// 3
func offset(len2 int) int {
    offset := 1
    for i := 1; i < len2; i++ {
        offset *= 10
    }
    return offset
}

//  After the lecture, I thought of the students' messages in class 
//  Suddenly realized , The essence of this problem is a 9 The base number is converted to 10 Binary number 
//  But fortunately, the solution in class has practical significance , This is the way to solve , A lot of questions are like this 
//  And the time complexity and "9 The base number is converted to 10 Binary number " How to do it , The time complexity is zero O(lg N)
//  however "9 The base number is converted to 10 Binary number " There is no doubt that the optimal solution 
func notContains4Nums3(num int) int {
    if num <= 0 {
        return 0
    }
    ans := 0
    for base, cur := 1, 0; num != 0; num, base = num/10, base*9 {
        cur = num % 10
        ans += twoSelectOne(cur < 4, cur, cur-1) * base
    }
    return ans
}

func twoSelectOne(c bool, a int, b int) int {
    if c {
        return a
    } else {
        return b
    }
}

The results are as follows ：

picture

---

Zuo Shen java Code