Number of Integers With Popcount-Depth Equal to K II solution and explanation
3 more videos on this problem
3624. Number of Integers With Popcount-Depth Equal to K II | Segment TreeAmit Dhyani · 18:23 · 700 views
3624. Number of Integers With Popcount-Depth Equal to K II (Leetcode Hard)Programming Live with Larry · 20:04 · 271 views
【每日一题】LeetCode 3624. Number of Integers With Popcount-Depth Equal to K IIHuifeng Guan · 24:10 · 184 views
LeetCode 3624. Number of Integers With Popcount-Depth Equal to K II | Fenwick Tree | HardLeet's Code · 25:20 · 131 views
The problem
You are given an integer array nums.
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.
You are also given a 2D integer array queries, where each queries[i] is either:
[1, l, r, k]- Determine the number of indicesjsuch thatl <= j <= rand the popcount-depth ofnums[j]is equal tok.[2, idx, val]- Updatenums[idx]toval.
Return an integer array answer, where answer[i] is the number of indices for the ith query of type [1, l, r, k].
Example 1:
Input: nums = [2,4], queries = [[1,0,1,1],[2,1,1],[1,0,1,0]]
Output: [2,1]
Explanation:
i |
queries[i] |
nums |
binary(nums) |
popcount- depth |
[l, r] |
k |
Validnums[j] |
updatednums |
Answer |
|---|---|---|---|---|---|---|---|---|---|
| 0 | [1,0,1,1] | [2,4] | [10, 100] | [1, 1] | [0, 1] | 1 | [0, 1] | — | 2 |
| 1 | [2,1,1] | [2,4] | [10, 100] | [1, 1] | — | — | — | [2,1] | — |
| 2 | [1,0,1,0] | [2,1] | [10, 1] | [1, 0] | [0, 1] | 0 | [1] | — | 1 |
Thus, the final answer is [2, 1].
Example 2:
Input: nums = [3,5,6], queries = [[1,0,2,2],[2,1,4],[1,1,2,1],[1,0,1,0]]
Output: [3,1,0]
Explanation:
i |
queries[i] |
nums |
binary(nums) |
popcount- depth |
[l, r] |
k |
Validnums[j] |
updatednums |
Answer |
|---|---|---|---|---|---|---|---|---|---|
| 0 | [1,0,2,2] | [3, 5, 6] | [11, 101, 110] | [2, 2, 2] | [0, 2] | 2 | [0, 1, 2] | — | 3 |
| 1 | [2,1,4] | [3, 5, 6] | [11, 101, 110] | [2, 2, 2] | — | — | — | [3, 4, 6] | — |
| 2 | [1,1,2,1] | [3, 4, 6] | [11, 100, 110] | [2, 1, 2] | [1, 2] | 1 | [1] | — | 1 |
| 3 | [1,0,1,0] | [3, 4, 6] | [11, 100, 110] | [2, 1, 2] | [0, 1] | 0 | [] | — | 0 |
Thus, the final answer is [3, 1, 0].
Example 3:
Input: nums = [1,2], queries = [[1,0,1,1],[2,0,3],[1,0,0,1],[1,0,0,2]]
Output: [1,0,1]
Explanation:
i |
queries[i] |
nums |
binary(nums) |
popcount- depth |
[l, r] |
k |
Validnums[j] |
updatednums |
Answer |
|---|---|---|---|---|---|---|---|---|---|
| 0 | [1,0,1,1] | [1, 2] | [1, 10] | [0, 1] | [0, 1] | 1 | [1] | — | 1 |
| 1 | [2,0,3] | [1, 2] | [1, 10] | [0, 1] | — | — | — | [3, 2] | |
| 2 | [1,0,0,1] | [3, 2] | [11, 10] | [2, 1] | [0, 0] | 1 | [] | — | 0 |
| 3 | [1,0,0,2] | [3, 2] | [11, 10] | [2, 1] | [0, 0] | 2 | [0] | — | 1 |
Thus, the final answer is [1, 0, 1].
Constraints:
1 <= n == nums.length <= 1051 <= nums[i] <= 10151 <= queries.length <= 105queries[i].length == 3or4queries[i] == [1, l, r, k]or,queries[i] == [2, idx, val]0 <= l <= r <= n - 10 <= k <= 50 <= idx <= n - 11 <= val <= 1015
Approach overview
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.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Popcount Simulation | O(n log V) | O(1) | Small input sizes or when only a single pass is required |
| Precomputation + Frequency Counting | O(n log V) | O(n) | When popcount-depth values repeat and can be cached |
| Fenwick Tree / Segment Tree | O(n log n) | O(n) | Large datasets with updates or range queries requiring fast aggregation |
Frequently asked questions
Is Number of Integers With Popcount-Depth Equal to K II easy or hard?
The problem is classified as Hard because it mixes bit manipulation with advanced data structures like Fenwick Trees or Segment Trees. Understanding popcount-depth transformations and maintaining counts efficiently under constraints requires strong algorithmic experience.
Number of Integers With Popcount-Depth Equal to K II Python/Java solution
Implementations typically compute popcount using built-in functions such as Python's bin(x).count('1') or Java's Integer.bitCount(). The optimized solution stores depth counts and uses a Fenwick Tree or Segment Tree to answer queries in O(log n) time.
How to solve Number of Integers With Popcount-Depth Equal to K II in O(n)?
Pure O(n) solutions are difficult when queries or dynamic updates are involved. However, you can reduce constant factors by precomputing popcount-depth values for possible bit counts and using direct counting. This avoids repeated popcount chains and keeps the per-element processing close to constant time.
What is the best approach for Number of Integers With Popcount-Depth Equal to K II?
The most practical approach uses precomputation of popcount-depth combined with a Fenwick Tree or Segment Tree to maintain counts efficiently. After mapping each number to its depth, updates and queries can be handled in O(log n) time. This leads to an overall complexity around O(n log n) for large inputs.
Is Number of Integers With Popcount-Depth Equal to K II asked at Google/Amazon/Meta?
Problems combining bit manipulation with range-query data structures frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of popcount-based transformations and Fenwick Tree counting are common in system-heavy algorithm rounds.
What data structure is used in Number of Integers With Popcount-Depth Equal to K II?
The main data structures are Binary Indexed Tree (Fenwick Tree) and Segment Tree. They allow efficient updates and prefix or range queries while tracking how many numbers have a specific popcount-depth.
What is the time complexity of Number of Integers With Popcount-Depth Equal to K II?
The optimal solution typically runs in O(n log n) time when a Binary Indexed Tree or Segment Tree is used for counting or range queries. Each number requires a popcount computation and a logarithmic tree operation. Space complexity is O(n) for storing the tree structure and intermediate values.