LeetCode-in-Java

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

public class Solution {
    private static final int MX = 60;
    private static final long[][] C = new long[MX][MX + 1];

    static {
        for (int i = 0; i < MX; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            }
        }
    }

    public long nthSmallest(long n, int k) {
        long ans = 0;
        for (int i = 50; i >= 0; i--) {
            long count = C[i][k];
            if (n > count) {
                n -= count;
                ans |= (1L << i);
                k--;
                if (k == 0) {
                    break;
                }
            }
        }
        return ans;
    }
}

This site is open source. Improve this page.