3621. Number of Integers With Popcount-Depth Equal to K I
Description
You are given two integers n and k.
For any positive integer x, define the following sequence:
p0 = xpi+1 = popcount(pi)for alli >= 0, wherepopcount(y)is the number of set bits (1's) in the binary representation ofy.
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 <= 10150 <= k <= 5
Solutions
Solution 1
Thinking
Popcount-depth is the number of times \(x\) is replaced by \(\mathrm{popcount}(x)\) until it becomes \(1\). \(n\) is too large to iterate \([1,n]\).
The depth is tiny because one popcount collapses \(x\) to its bit length. Digit DP counts integers \(\le n\) with a given number \(c\) of ones; those \(c\) are then matched against \(k\).
Precompute \(\textit{depth}(c)\) for every feasible popcount. Handle \(k=0\) as the singleton \(1\). A binary digit DP over \(n\) sums every \(c\) with \(\textit{depth}(c)=k-1\), since one more popcount raises the depth by one.
1 | |
1 | |
1 | |
1 | |