Number of integers with popcount depth equal to k i

Math Dynamic Programming Bit Manipulation Combinatorics

22.4% acceptance

Feb 25, 2026

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

fn comb_3621(n_val: u32, k_val: u32) -> i64 {
  if k_val > n_val { return 0; }
  let k_val = k_val.min(n_val - k_val);
  let mut result = 1i64;
  for i in 0..k_val {
    result = result * (n_val - i) as i64 / (i + 1) as i64;
  }
  result
}

fn count_exactly_b_bits_3621(n: i64, b: u32) -> i64 {
  if b == 0 { return 1; }
  let mut result = 0i64;
  let mut bits_used = 0u32;
  for bit in (0..50i32).rev() {
    if n & (1i64 << bit) != 0 {
      let remaining_needed = b.saturating_sub(bits_used);
      let available = bit as u32;
      if remaining_needed <= available {
        result += comb_3621(available, remaining_needed);
      }
      bits_used += 1;
      if bits_used > b { break; }
    }
  }
  if bits_used == b { result += 1; }
  result
}

fn depth_small_3621(mut x: i32) -> i32 {
  let mut d = 0;
  while x != 1 { x = x.count_ones() as i32; d += 1; }
  d
}

impl Solution {
  pub fn popcount_depth(n: i64, k: i32) -> i64 {
    if k == 0 { return if n >= 1 { 1 } else { 0 }; }
    let mut total = 0i64;
    for b in 1u32..=50 {
      if depth_small_3621(b as i32) == k - 1 {
        let cnt = count_exactly_b_bits_3621(n, b) - count_exactly_b_bits_3621(1, b);
        total += cnt;
      }
    }
    total
  }
}