Containing7s.swift

import UIKit

precedencegroup PowerPrecedence { higherThan: MultiplicationPrecedence }
infix operator ^^ : PowerPrecedence
func ^^ (radix: Int, power: Int) -> Int {
    return Int(pow(Double(radix), Double(power)))
}

/// First approach
///
/// To loop through all number from 1 ~ num.
/// Then check if num contains 7 by mode 10 then divide by ten.
///
/// Time complexity will be length of 1 ~ num (N), and
/// calculate every digit inside every number (M).
///
/// TC will be O(MN).
func g(_ num: Int) -> Int {
    var result = 0

    for n in 1...num {
        var n = n

        while n > 0 {
            let r = n % 10

            if r == 7 {
                result += 1
                break
            }

            n /= 10
        }
    }

    return result
}


/// Second approach
///
/// We can see a lot dulicate calculation in first approach.
/// In this approach, we can first calculate 7s in 10, 100, 1000, and so on.
///
/// When we have 7s of these numbers, we can then separate this problem into smaller problem.
/// Like we can have 107 separate into 100 + 7.
/// We know how many 7s in 100, next thing is to calculate the remaining part of number.
/// Also, we need to deal with edge case like 777. We can make it 699 + 78, because if we have 7 ahead, all remaining number will always have 7.
///
/// The above calculation will first do one pass to calculate 7s in 10, 100, 100...
/// Then do one pass to check 7s in the number.
/// TC of this process will be O(1).
func g2(_ num: Int) -> Int {
    guard num > 10 else { // for nums between 1 ~ 10
        return num >= 7 ? 1 : 0
    }

    var numForDividing = num
    var numArr = [Int]()

    while numForDividing != 0 {
        let n = numForDividing % 10
        numArr.insert(n, at: 0)
        numForDividing /= 10
    }

    // mapping 1~10 -> 1x 7s num
    // 1~100 -> 19x 7s
    // ... and so on
    var sevensAndTensDigitMapping: [Int: Int] = [10: 1]

    for digit in 1...numArr.count {
        let previousTensDigit = 10 ^^ (digit - 1)
        let currentTensDigit = 10 ^^ digit
        if currentTensDigit == 10 { continue } // skip 10

        let previous7Counts = sevensAndTensDigitMapping[previousTensDigit]!
        let this7Counts = previousTensDigit + 9 * previous7Counts
        sevensAndTensDigitMapping[currentTensDigit] = this7Counts
    }

    if sevensAndTensDigitMapping[num] != nil { // for 10, 100, 1000... and so on
        return sevensAndTensDigitMapping[num]!
    }

    var r = 0
    while numArr.count > 1 {
        let thisNum = numArr.removeFirst()
        let tens = 10 ^^ (numArr.count)

        if thisNum < 7 {
            r += thisNum * sevensAndTensDigitMapping[tens]!
        } else if thisNum == 7 {
            let remainNum = numArr.reduce(0, { r, n in r * 10 + n }) // find out remaining num after 7, like 701
            r += remainNum + 1 // 1 for case like zero
            let count = numArr.count
            numArr = [6] + Array(repeating: 9, count: count)
        } else {
            r += tens + (thisNum - 1) * sevensAndTensDigitMapping[tens]!
        }
    }

    if numArr[0] >= 7 {
        r += 1
    }

    return r
}

for n in [7, 20, 70, 100, 1000] {
    print("Calcuate \(n)")
    print(g(n))
    print(g2(n))
}

func measure(_ label: String, _ closure: () -> Void, rounds: Int = 1) -> TimeInterval {
    let before = Date()
    for _ in 1...rounds {
        closure()
    }
    let after = Date()

    let time = after.timeIntervalSince(before)
    print("[Measure] [\(label)] takes \(time)s")
    return time
}

// We can see measure here

let a = measure("G") {
    g(100000)
}

let b = measure("G2") {
    g2(100000)
}

print("A vs B, B is \(a/b)x faster.")

// outputs
// Calcuate 7
// 1
// 1
// Calcuate 20
// 2
// 2
// Calcuate 70
// 8
// 8
// Calcuate 100
// 19
// 19
// Calcuate 1000
// 271
// 271
// [Measure] [G] takes 2.8038769960403442s
// [Measure] [G2] takes 0.0004469156265258789s
// A vs B, B is 6273.8396905841555x faster.