package daily

import kotlin.math.min

fun main() {
    // 面试题 17.09. 第 k 个数
    // https://leetcode.cn/problems/get-kth-magic-number-lcci/
    // 题解
    // https://leetcode.cn/problems/get-kth-magic-number-lcci/solution/di-k-ge-shu-jiu-shi-xiang-bu-tong-wei-he-san-zhi-z/
    println(getKthMagicNumber(5))
}

fun getKthMagicNumber(k: Int): Int {
    // dp 数组，dp[i] 表示第 i 个数，所以要求第 k 个数，就是返回 dp[k]
    val dp = IntArray(k+1)
    dp[1] = 1
    // 三个指针
    var p3 = 1
    var p5 = 1
    var p7 = 1
    var dpIndex = 1
    while (dpIndex < k) {
        val tmp3 = dp[p3] * 3
        val tmp5 = dp[p5] * 5
        val tmp7 = dp[p7] * 7
        val min = min(min(tmp3, tmp5), tmp7)
        if (min == tmp3) {
            p3++
        }
        if (min == tmp5) {
            p5++
        }
        if (min == tmp7) {
            p7++
        }
        dpIndex++
        dp[dpIndex] = min
    }
    return dp[k]
}

fun getKthMagicNumber1(k: Int): Int {
    // uglys 数组，uglys[i] 表示第 i 个数，所以要求第 k 个数，就是返回 uglys[k]
    val uglys = IntArray(k+1)
    var p3 = 1
    var p5 = 1
    var p7 = 1
    uglys[1] = 1
    var uglyIndex = 1
    while (uglyIndex < k) {
        val tmp3 = uglys[p3] * 3
        val tmp5 = uglys[p5] * 5
        val tmp7 = uglys[p7] * 7
        val min = min(tmp3, min(tmp5, tmp7))
        if (tmp3 == min) {
            p3++
        }
        if (tmp5 == min) {
            p5++
        }
        if (tmp7 == min) {
            p7++
        }
        uglyIndex++
        uglys[uglyIndex] = min
    }
    return uglys[uglyIndex]
}