Count K-Reducible Numbers Less Than N - Video Solutions

Problem Overview: Given a binary string N, count how many positive integers strictly less than N become 1 after applying the operation x = popcount(x) at most k times. A number is k-reducible if repeatedly replacing it with the number of set bits eventually reaches 1 within k steps.

Approach 1: Brute Force Simulation (O(N log N) time, O(1) space)

Iterate through every integer x from 1 to N-1. For each value, repeatedly compute popcount(x) until the number becomes 1 or the step count exceeds k. This directly simulates the definition of k-reducibility. The method is easy to reason about but completely impractical when N is large (often up to hundreds of bits). It mainly helps verify correctness on small inputs and understand the reduction process.

Approach 2: Dynamic Programming Simulation (O(L * log L) time, O(L) space)

Instead of simulating the full value of each number, focus on the number of set bits. Any integer eventually reduces to a small sequence determined by its initial popcount. Precompute how many steps each possible bit count requires to reach 1. For numbers with binary length L, the maximum popcount is L, so you can precompute reductions for all counts from 1..L. Then count numbers below N with a valid bit count using digit-style iteration over the binary string. This combines dynamic programming with bit counting.

Approach 3: Dynamic Programming to Count K-Reducible Numbers (O(L^2) time, O(L^2) space)

The optimal approach treats the problem as a binary digit DP. Traverse the bits of N from left to right and track how many 1s have been chosen so far. For every prefix that becomes smaller than N, count combinations of remaining bits using C(n, r). Each candidate total bit count is checked against the precomputed reduction steps to see if it reaches 1 within k. This works because the reduction path depends only on the number of set bits, not the original value. The method relies heavily on combinatorics and dynamic programming.

Approach 4: Iterative Constraint Based Counting (O(L^2) time, O(L) space)

Another implementation uses the same key observation but performs counting iteratively. While scanning the binary digits of N, when encountering a 1, temporarily flip it to 0 and count all numbers formed by the remaining suffix with a chosen number of set bits. Combination formulas determine how many such numbers exist. Each possible final bit count is validated against the precomputed step requirement. This approach avoids a full DP table and keeps memory small while still leveraging math and combinatorial counting.

Recommended for interviews: The combinatorics + digit DP approach is the expected solution. Interviewers want to see the key insight that the reduction chain depends only on the number of set bits. Brute force demonstrates understanding of the process, but the optimized counting approach shows strong skills with binary digit DP and combinatorial reasoning.