Number of Integers With Popcount-Depth Equal to K I - Solution & Explanation

Problem Overview: Given an upper bound n, count how many integers satisfy a specific popcount-depth. The popcount-depth of a number is the number of times you repeatedly apply popcount(x) (count of set bits) until the value becomes 1. The task is to count numbers whose depth equals k.

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

Iterate through every integer from 1 to n. For each number, repeatedly apply the popcount operation and count how many steps are required to reach 1. If the number of steps equals k, include it in the answer. Each simulation takes up to O(log n) operations because the value shrinks quickly after each popcount. This approach is simple but infeasible when n is large.

Approach 2: Combinatorics + Bit Digit DP (O((log n)^2) time, O(log n) space)

Key observation: after the first popcount operation, the value becomes the number of set bits in the original number. That means the remaining depth depends only on that bit count. Precompute the popcount-depth for all possible bit counts up to the maximum number of bits in n. For every candidate bit count b, check if its remaining depth equals k-1. If it does, count how many numbers ≤ n contain exactly b set bits.

Counting numbers with exactly b set bits is done using combinatorics while scanning the binary representation of n. When you encounter a 1, you can choose to place 0 there and distribute the remaining set bits across the remaining positions using C(remainingBits, remainingOnes). This transforms the problem into a standard bit-prefix counting technique common in bit manipulation and dynamic programming problems, with combinations from combinatorics.

The algorithm runs in roughly O((log n)^2) time because you iterate over bit positions and evaluate combinations for possible set-bit counts. Space usage stays O(log n) for storing combination values and depth results.

Recommended for interviews: The combinatorics + bit DP approach is the expected solution. Brute force demonstrates understanding of the popcount-depth definition, but interviewers look for the observation that the first popcount reduces the state space to the number of set bits. Using combinations to count valid numbers under a binary prefix shows strong problem-solving with bit constraints.