Skip to main content
Talentd

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

HardMathDynamic ProgrammingBit ManipulationCombinatorics3 min read
Practice this problem

Problem Statement

You are given two integers n and k.

For any positive integer x, define the following sequence:

  • p0 = x
  • pi+1 = popcount(pi) for all i >= 0, where popcount(y) is the number of set bits (1's) in the binary representation of y.

This sequence will eventually reach the value 1.

The popcount-depth of x is defined as the smallest integer d >= 0 such that pd = 1.

For example, if x = 7 (binary representation "111"). Then, the sequence is: 7 → 3 → 2 → 1, so the popcount-depth of 7 is 3.

Your task is to determine the number of integers in the range [1, n] whose popcount-depth is exactly equal to k.

Return the number of such integers.

 

Example 1:

Input: n = 4, k = 1

Output: 2

Explanation:

The following integers in the range [1, 4] have popcount-depth exactly equal to 1:

x Binary Sequence
2 "10" 2 → 1
4 "100" 4 → 1

Thus, the answer is 2.

Example 2:

Input: n = 7, k = 2

Output: 3

Explanation:

The following integers in the range [1, 7] have popcount-depth exactly equal to 2:

x Binary Sequence
3 "11" 3 → 2 → 1
5 "101" 5 → 2 → 1
6 "110" 6 → 2 → 1

Thus, the answer is 3.

 

Constraints:

  • 1 <= n <= 1015
  • 0 <= k <= 5

Approach Overview

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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Popcount SimulationO(n log n)O(1)Small constraints or verifying correctness during development
Combinatorics + Bit Digit DPO((log n)^2)O(log n)Large n where direct iteration is impossible; optimal competitive programming and interview solution

Video Solution

3621. Number of Integers With Popcount-Depth Equal to K I | Digit DP | Biweekly Contest 161 • Amit Dhyani • 1,232 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Number of Integers With Popcount-Depth Equal to K I easy or hard?
This problem is considered Hard because it combines several concepts: popcount iteration, combinatorics, and digit DP over the binary representation of n. Recognizing that the first popcount reduces the state to the number of set bits is the key insight.
Number of Integers With Popcount-Depth Equal to K I Python/Java solution
Implement the combinatorics + bit DP approach. Precompute binomial coefficients, determine valid set-bit counts based on popcount-depth, then iterate through the bits of n to accumulate counts. The same logic works in Python, Java, C++, and Go with minor syntax differences.
How to solve Number of Integers With Popcount-Depth Equal to K I in O(log^2 n)?
Precompute the popcount-depth for all possible bit counts up to the bit length of n. Then scan the binary digits of n and count how many numbers with exactly b set bits can be formed using combinations. Only include b values whose remaining popcount-depth equals k−1.
What is the best approach for Number of Integers With Popcount-Depth Equal to K I?
The optimal approach uses combinatorics combined with a digit DP style traversal of the binary representation of n. Instead of iterating through every number, compute how many numbers have a specific count of set bits and check whether that count leads to popcount-depth k. This reduces the complexity to about O((log n)^2).
Is Number of Integers With Popcount-Depth Equal to K I asked at Google/Amazon/Meta?
Problems combining bit manipulation, combinatorics, and digit DP frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving popcount properties and counting numbers under a limit are common advanced interview topics.
What data structure is used in Number of Integers With Popcount-Depth Equal to K I?
The solution mainly relies on arrays for precomputing combinations and popcount-depth values. The algorithm itself uses bit manipulation and combinatorial counting rather than complex data structures.
What is the time complexity of Number of Integers With Popcount-Depth Equal to K I?
The optimal solution runs in O((log n)^2) time because it iterates through the bits of n and evaluates combination values for possible set-bit counts. Space complexity is O(log n) for storing combination values and popcount-depth results.

Ready to solve this problem?

Practice Number of Integers With Popcount-Depth Equal to K I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Pattern in Infinite Stream II