LeetCode 3821 - Find Nth Smallest Integer With K One Bits

LeetCode Problem 3821

Difficulty: 🔴 Hard
Topics: Math, Bit Manipulation, Combinatorics

Solution

Problem Understanding

This problem asks us to find the nth smallest positive integer whose binary representation contains exactly k ones. In other words, we are working with numbers that, when written in binary, have a specific number of bits set to 1. The input consists of two integers: n representing the ordinal position in the sequence of such numbers, and k representing the exact number of 1 bits. The output is the integer that meets these criteria and occupies the nth position in ascending order.

The constraints provide several important insights. First, 1 <= n <= 250 and 1 <= k <= 50 indicate that the sequence we need to consider is relatively small. Moreover, the guarantee that the answer is strictly less than 250 means that the search space is tiny, allowing us to consider methods that would otherwise be infeasible for large integers. Edge cases include n = 1, k = 1, and situations where k is large relative to the maximum number 250, though this is constrained by the problem guarantee.

Approaches

A brute-force approach is straightforward: iterate through every positive integer starting from 1, convert it to binary, count the number of ones, and keep track of how many numbers have exactly k ones until reaching the nth. This approach is correct because it exhaustively checks each integer and ensures the ordering is strictly ascending. However, iterating naively can be inefficient in general if the numbers were large. In this problem, the small upper bound (less than 250) makes brute force viable but not elegant.

The optimal approach leverages combinatorics and bit manipulation. The key insight is that generating numbers with exactly k ones is equivalent to choosing k positions out of the available bit positions. We can generate the nth number directly by computing the next number with k ones without enumerating all smaller numbers explicitly. This is akin to generating the sequence of integers in lexicographical order of their binary representations with fixed ones using the "next combination" technique.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(M * log M)	O(1)	Iterate numbers up to M < 250, convert to binary, count ones
Optimal	O(1)	O(1)	Directly compute nth number using bit manipulation and combinatorial logic

Algorithm Walkthrough

1. Initialize a counter to track how many valid numbers with k ones have been found.
2. Start iterating from the smallest positive integer, which is 1.
3. For each integer, compute its binary representation and count the number of ones.
4. If the number of ones equals k, increment the counter.
5. When the counter reaches n, return the current integer.
6. Stop iterating as soon as the result is found, leveraging the guarantee that the result is strictly less than 250.

Why it works: The algorithm works because it examines integers in strictly ascending order, ensuring that the nth integer encountered with exactly k ones corresponds exactly to the nth smallest integer meeting the criteria. The problem guarantees that the nth number exists and is less than 250, so this linear scan will always terminate.

Python Solution

class Solution:
    def nthSmallest(self, n: int, k: int) -> int:
        count = 0
        num = 1
        while True:
            if bin(num).count('1') == k:
                count += 1
                if count == n:
                    return num
            num += 1

In this implementation, count tracks how many numbers with exactly k ones have been found. The loop increments num starting from 1. For each num, we compute its binary representation using bin(num) and count the number of ones with .count('1'). When count reaches n, we return the current number.

Go Solution

func nthSmallest(n int64, k int) int64 {
    var count int64 = 0
    for num := int64(1); num < 250; num++ {
        ones := 0
        temp := num
        for temp > 0 {
            if temp&1 == 1 {
                ones++
            }
            temp >>= 1
        }
        if ones == int(k) {
            count++
            if count == n {
                return num
            }
        }
    }
    return -1
}

In Go, we iterate from 1 up to 250 as guaranteed by the problem. For each number, we count the ones using bitwise operations instead of converting to a string. The rest of the logic mirrors the Python version. Go requires explicit type conversion for k to compare with the ones count.

Worked Examples

Example 1: n = 4, k = 2

num	binary	ones	count
1	1	1	0
2	10	1	0
3	11	2	1
4	100	1	1
5	101	2	2
6	110	2	3
7	111	3	3
8	1000	1	3
9	1001	2	4 -> return 9

Example 2: n = 3, k = 1

num	binary	ones	count
1	1	1	1
2	10	1	2
3	11	2	2
4	100	1	3 -> return 4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(M)	We iterate up to a maximum M < 250, which is constant. Counting ones is O(log M), negligible.
Space	O(1)	Only integer counters are used, no extra data structures.

The complexity is effectively constant because the problem constraint ensures the answer is below 250.

Test Cases

# Provided examples
assert Solution().nthSmallest(4, 2) == 9  # 4th number with 2 ones
assert Solution().nthSmallest(3, 1) == 4  # 3rd number with 1 one

# Edge and boundary cases
assert Solution().nthSmallest(1, 1) == 1  # first number with 1 one
assert Solution().nthSmallest(1, 2) == 3  # first number with 2 ones
assert Solution().nthSmallest(10, 2) == 18 # verify nth in sequence with 2 ones

# Maximum constraints
assert Solution().nthSmallest(250, 1) < 250  # largest nth number with 1 one
assert Solution().nthSmallest(250, 2) < 250  # largest nth number with 2 ones

Test	Why
n=4, k=2	Validates counting and order with multiple ones
n=3, k=1	Validates sequence with single ones
n=1, k=1	Validates smallest input edge case
n=1, k=2	Validates smallest number with 2 ones
n=10, k=2	Validates mid-sequence computation
n=250, k=1	Validates handling maximum n constraint
n=250, k=2	Validates maximum n with more ones

Edge Cases

Edge Case 1: n = 1, k = 1

The smallest number with exactly one 1 is always 1. A naive implementation may incorrectly start counting from 0, but our loop begins at 1, ensuring correctness.

Edge Case 2: Maximum value less than 250

Since the answer must be strictly less than 250, the implementation safely stops at 250 in Go. In Python, the loop continues indefinitely until the nth number is found, which is guaranteed to exist.

Edge Case 3: Large k relative to small numbers

For example, k = 7. There are few numbers less than 250 with seven ones. Our implementation correctly counts numbers and does not assume n is always smaller than the number of candidates because the constraints guarantee existence. The algorithm will always terminate with the correct number.