LeetCode in Kotlin

3821. Find Nth Smallest Integer With K One Bits

Hard

You are given two positive integers n and k.

Return an integer denoting the nth smallest positive integer that has exactly k ones in its binary representation. It is guaranteed that the answer is strictly less than 250.

Example 1:

Input: n = 4, k = 2

Output: 9

Explanation:

The 4 smallest positive integers that have exactly k = 2 ones in their binary representations are:

• 3 = 112
• 5 = 1012
• 6 = 1102
• 9 = 10012

Example 2:

Input: n = 3, k = 1

Output: 4

Explanation:

The 3 smallest positive integers that have exactly k = 1 one in their binary representations are:

• 1 = 12
• 2 = 102
• 4 = 1002

Constraints:

• 1 <= n <= 250
• 1 <= k <= 50
• The answer is strictly less than 250.

Solution

class Solution {
    fun nthSmallest(n: Long, k: Int): Long {
        var n = n
        var k = k
        var ans: Long = 0
        for (i in 50 downTo 0) {
            val count: Long = C[i][k]
            if (n > count) {
                n -= count
                ans = ans or (1L shl i)
                k--
                if (k == 0) {
                    break
                }
            }
        }
        return ans
    }

    companion object {
        private const val MX = 60
        private val C = Array<LongArray>(MX) { LongArray(MX + 1) }

        init {
            for (i in 0..<MX) {
                C[i][0] = 1
                for (j in 1..i) {
                    C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
                }
            }
        }
    }
}

This site is open source. Improve this page.