LeetCode 3621 - Number of Integers With Popcount-Depth Equal to K I

This problem asks us to count integers x in the range [1, n] such that the popcount-depth of x is exactly k. The popcount-depth is defined via a sequence p0, p1, ... where p0 = x and pi+1 = popcount(pi) for all i ≥ 0.

leetcodehardmathdynamic-programmingbit-manipulationcombinatorics

LeetCode Problem 3621

Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming, Bit Manipulation, Combinatorics

Solution

Problem Understanding

This problem asks us to count integers x in the range [1, n] such that the popcount-depth of x is exactly k. The popcount-depth is defined via a sequence p0, p1, ... where p0 = x and pi+1 = popcount(pi) for all i ≥ 0. The popcount of a number is the number of 1's in its binary representation. The depth is the number of steps until this sequence reaches 1.

For example, for x = 7 (binary 111), the sequence is 7 → 3 → 2 → 1, so the depth is 3.

The input n can be as large as $10^{15}$, which rules out brute-force iteration over all integers. The depth k is small, at most 5, which suggests we can exploit the limited depth to construct a combinatorial or dynamic programming solution rather than iterating each number individually.

Edge cases include k = 0 (only x = 1 qualifies), very small n (like 1 or 2), and powers of 2 where the sequence is short because popcount reduces them quickly.

Approaches

Brute-Force

A naive solution iterates x from 1 to n, computes the popcount-depth for each x, and counts how many match k. The popcount-depth can be computed by repeatedly counting bits until reaching 1. This is correct but too slow for n ≈ 10^{15}, because even a single pass would require $O(n \log n)$ operations in the worst case.

Optimal Approach

The key observation is that popcount sequences shrink rapidly: popcount(x) ≤ log2(x) + 1. Since k ≤ 5, the depth is very small, so we can invert the problem: for each possible depth sequence, count numbers with exactly that popcount progression using combinatorics.

We can precompute the depth for small integers (up to ~64, the maximum number of set bits in a 64-bit number). Then, using digit DP over binary representation, we count numbers ≤ n with a given number of set bits. Using the binomial coefficient formula, C(bits_remaining, ones_to_place), we can enumerate possibilities efficiently.

Thus, the problem reduces to combining bit-count DP with precomputed depth values.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(1) Iterate all x, compute popcount-depth for each
Optimal O(64^2) O(64) Use DP on binary representation + combinatorial counting

Algorithm Walkthrough

  1. Precompute popcount-depths for all integers up to 64 (sufficient because max number of 1 bits in n ≤ 10^{15} is 50).
  2. Define a DP function count(pos, ones_remaining, tight) over the binary digits of n:
  • pos tracks the current bit index in n
  • ones_remaining tracks how many 1's we plan to place
  • tight indicates whether the number being formed must stay ≤ n
  1. For each possible number of 1's (ones_count) in the binary representation:
  • Check if the precomputed popcount-depth of ones_count is k-1 (the first reduction to popcount counts as one step)
  • Use the DP to count how many numbers ≤ n have exactly ones_count 1's.
  1. Sum the counts for all ones_count that match the required depth.
  2. If k = 0, return 1 if n ≥ 1 (only number 1 has depth 0), else return 0.

Why it works: The DP ensures we count numbers ≤ n correctly, and the precomputed depth ensures we only select numbers whose popcount sequence reaches 1 in exactly k steps. The combinatorial counting via binomial coefficients guarantees that all placements of 1's are considered without iterating each number individually.

Python Solution

from functools import lru_cache
from math import comb

class Solution:
    def popcountDepth(self, n: int, k: int) -> int:
        # Precompute depth for numbers up to 64
        max_bits = 64
        depth = [0] * (max_bits + 1)
        depth[0] = -1  # not used
        depth[1] = 0
        for i in range(2, max_bits + 1):
            depth[i] = 1 + depth[bin(i).count('1')]
        
        if k == 0:
            return 1 if n >= 1 else 0

        bin_n = bin(n)[2:]
        length = len(bin_n)
        
        @lru_cache(None)
        def dp(pos: int, ones_remaining: int, tight: bool) -> int:
            if ones_remaining < 0:
                return 0
            if pos == length:
                return 1 if ones_remaining == 0 else 0
            limit = int(bin_n[pos]) if tight else 1
            res = 0
            for digit in range(0, limit + 1):
                res += dp(pos + 1,
                          ones_remaining - digit,
                          tight and (digit == limit))
            return res

        ans = 0
        for ones_count in range(1, max_bits + 1):
            if depth[ones_count] == k - 1:
                ans += dp(0, ones_count, True)
        return ans

Explanation: The depth array precomputes popcount-depth for integers up to 64. The recursive dp function counts the number of integers ≤ n with exactly ones_remaining 1's, respecting the tight upper bound. For each possible number of 1's with the required depth, the DP is called and summed.

Go Solution

package main

import (
	"fmt"
)

func popcountDepth(n int64, k int) int64 {
	maxBits := 64
	depth := make([]int, maxBits+1)
	depth[0] = -1
	depth[1] = 0
	for i := 2; i <= maxBits; i++ {
		bits := 0
		x := i
		for x > 0 {
			if x&1 == 1 {
				bits++
			}
			x >>= 1
		}
		depth[i] = 1 + depth[bits]
	}

	if k == 0 {
		if n >= 1 {
			return 1
		}
		return 0
	}

	binN := fmt.Sprintf("%b", n)
	length := len(binN)
	memo := make(map[[3]int64]int64)

	var dp func(pos int64, onesRemaining int64, tight int64) int64
	dp = func(pos int64, onesRemaining int64, tight int64) int64 {
		if onesRemaining < 0 {
			return 0
		}
		if pos == int64(length) {
			if onesRemaining == 0 {
				return 1
			}
			return 0
		}
		key := [3]int64{pos, onesRemaining, tight}
		if val, ok := memo[key]; ok {
			return val
		}
		limit := int64(1)
		if tight == 1 {
			if binN[pos] == '0' {
				limit = 0
			} else {
				limit = 1
			}
		}
		res := int64(0)
		for digit := int64(0); digit <= limit; digit++ {
			nextTight := int64(0)
			if tight == 1 && digit == limit {
				nextTight = 1
			}
			res += dp(pos+1, onesRemaining-digit, nextTight)
		}
		memo[key] = res
		return res
	}

	var ans int64
	for onesCount := 1; onesCount <= maxBits; onesCount++ {
		if depth[onesCount] == k-1 {
			ans += dp(0, int64(onesCount), 1)
		}
	}
	return ans
}

Go Notes: Memoization uses a map with [3]int64 keys to cache dp results. Bit counting uses standard shift-and-mask. Integer overflow is not an issue since n ≤ 10^15.

Worked Examples

Example 1: n = 4, k = 1

Binary of 4: 100

  • Depth 1 means numbers directly reach 1 in one popcount
  • x = 2 → 10 → 1
  • x = 4 → 100 → 1

DP counts these numbers correctly using ones count 1 (depth[1] = 0 → k-1 = 0). Result = 2.

Example 2: n = 7, k = 2

Binary of 7: 111

  • Depth 2 means numbers reduce to 1 in 2 steps
  • Check ones counts with depth