#3621

Number of Integers With Popcount-Depth Equal to K I

international master · 2160 · lc hard +32 · 22.4% accepted · 52 likes · top 2%

Description

For a positive integer x, build a sequence starting at p0 = x. Each step: pi+1 = popcount(pi) (count of set bits). The sequence converges to 1.

The popcount-depth of x is the smallest d >= 0 where pd = 1. Example: x = 7 gives 7 → 3 → 2 → 1, depth 3.

Count integers in [1, n] with popcount-depth exactly equal to k and return that count.

Code

1

2

3

class Solution:
    def popcountDepth(self, n: int, k: int) -> int:

class Solution:
    def popcountDepth(self, n: int, k: int) -> int: