Welcome to Subscribe On Youtube

3821. Find Nth Smallest Integer With K One Bits

Description

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.

Solutions

Solution 1: Combinatorics + Greedy

We need to find the $n$-th smallest positive integer that contains exactly $k$ ones in its binary representation. We can determine each bit from the most significant to the least significant, deciding whether it is $0$ or $1$.

Suppose we are currently processing the $i$-th bit (from $49$ down to $0$). If we set this bit to $0$, then the remaining $k$ ones need to be chosen from the lower $i$ bits, and the number of possible combinations is $C(i, k)$. If $n$ is greater than $C(i, k)$, it implies that the $i$-th bit of the $n$-th number must be $1$. In this case, we set this bit to $1$, subtract $C(i, k)$ from $n$, and decrement $k$ by $1$ (since we have already used one $1$). Otherwise, we set this bit to $0$.

We repeat the above process until all bits are processed or $k$ becomes $0$.

The time complexity is $O(\log^2 M)$, and the space complexity is $O(\log^2 M)$, where $M$ is the upper bound of the answer, $2^{50}$.

  • class Solution {
    private static final int MX = 50;
    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 = 49; i >= 0; i--) {
            if (n > c[i][k]) {
                n -= c[i][k];
                ans |= 1L << i;
                k--;
                if (k == 0) {
                    break;
                }
            }
        }
        return ans;
    }
}


  • constexpr int MX = 50;
long long c[MX][MX + 1];

auto init = [] {
    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];
        }
    }
    return 0;
}();

class Solution {
public:
    long long nthSmallest(long long n, int k) {
        long long ans = 0;
        for (int i = 49; i >= 0; i--) {
            if (n > c[i][k]) {
                n -= c[i][k];
                ans |= 1LL << i;
                if (--k == 0) {
                    break;
                }
            }
        }
        return ans;
    }
};


  • mx = 50
c = [[0] * (mx + 1) for _ in range(mx)]
for i in range(mx):
    c[i][0] = 1
    for j in range(1, i + 1):
        c[i][j] = c[i - 1][j - 1] + c[i - 1][j]


class Solution:
    def nthSmallest(self, n: int, k: int) -> int:
        ans = 0
        for i in range(49, -1, -1):
            if n > c[i][k]:
                n -= c[i][k]
                ans |= 1 << i
                k -= 1
                if k == 0:
                    break
        return ans


  • const MX = 50

var c [MX][MX + 1]int64

func init() {
	for i := 0; i < MX; i++ {
		c[i][0] = 1
		for j := 1; j <= i; j++ {
			c[i][j] = c[i-1][j-1] + c[i-1][j]
		}
	}
}

func nthSmallest(n int64, k int) int64 {
	var ans int64 = 0
	for i := 49; i >= 0; i-- {
		if n > c[i][k] {
			n -= c[i][k]
			ans |= 1 << i
			k--
			if k == 0 {
				break
			}
		}
	}
	return ans
}


  • const MX = 50;
const c: bigint[][] = Array.from({ length: MX }, () => Array(MX + 1).fill(0n));

for (let i = 0; i < MX; i++) {
    c[i][0] = 1n;
    for (let j = 1; j <= i; j++) {
        c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
}

function nthSmallest(n: number, k: number): number {
    let nn = BigInt(n);
    let ans = 0n;
    for (let i = 49; i >= 0; i--) {
        if (nn > c[i][k]) {
            nn -= c[i][k];
            ans |= 1n << BigInt(i);
            if (--k === 0) {
                break;
            }
        }
    }
    return Number(ans);
}

All Problems

All Solutions