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

Problem Overview: You are given integers and need to count how many have a popcount-depth equal to K. The popcount-depth of a number is defined by repeatedly applying the bit count operation (popcount) until the value becomes 1. The challenge is efficiently tracking how many numbers satisfy this property while processing large input sizes.

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

The most direct solution computes the popcount-depth for every integer independently. For each number, repeatedly apply popcount until the value becomes 1 and count how many steps were needed. Compare that depth with K and increment the result if it matches. Each popcount reduces the number size quickly, so the number of iterations is bounded by O(log V), where V is the maximum integer value. This approach is easy to implement but becomes slow if the problem involves repeated queries or updates.

Approach 2: Precomputation + Frequency Counting (O(n log V) time, O(n) space)

A better strategy precomputes the popcount-depth for all possible bit counts that can appear. For any number x, compute bits = popcount(x), then repeatedly apply popcount to determine the depth. Since the maximum bit count for standard integers is small (≤ 64), you can cache depths for each bit count. While iterating through the array, compute popcount(x), look up its depth, and update a frequency structure. This avoids repeated recomputation and speeds up processing significantly.

Approach 3: Divide and Conquer with Fenwick/Segment Tree (O(n log n) time, O(n) space)

When the problem includes dynamic queries or range-based counting, a tree-based structure becomes necessary. After mapping each number to its popcount-depth, maintain counts using a Fenwick Tree (Binary Indexed Tree) or Segment Tree. Each node stores how many numbers currently have a given depth. Updates modify the corresponding index, and queries aggregate counts efficiently in O(log n) time. This technique combines bit manipulation with classic range-query structures from Binary Indexed Tree, Segment Tree, and Divide and Conquer patterns.

Recommended for interviews: Start with the brute force explanation to show you understand the definition of popcount-depth. Then move to the optimized solution that precomputes depths and maintains counts using a Fenwick Tree or Segment Tree. Interviewers typically expect the O(n log n) approach because it demonstrates familiarity with range-query data structures and efficient counting strategies.