Problem

You are given a binary string s representing a number n in its binary form.

You are also given an integer k.

An integer x is called k-reducible if performing the following operation at most k times reduces it to 1:

  • Replace x with the count of set bits in its binary representation.

For example, the binary representation of 6 is "110". Applying the operation once reduces it to 2 (since "110" has two set bits). Applying the operation again to 2 (binary "10") reduces it to 1 (since "10" has one set bit).

Return an integer denoting the number of positive integers less than n that are k-reducible.

Since the answer may be too large, return it modulo 10^9 + 7.

Examples

Example 1

1
2
3
4
5
6
7
8


Input: s = "111", k = 1

Output: 3

Explanation:

`n = 7`. The 1-reducible integers less than 7 are 1, 2, and 4.

Example 2

1
2
3
4
5
6
7
8


Input: s = "1000", k = 2

Output: 6

Explanation:

`n = 8`. The 2-reducible integers less than 8 are 1, 2, 3, 4, 5, and 6.

Example 3

1
2
3
4
5
6
7
8


Input: s = "1", k = 3

Output: 0

Explanation:

There are no positive integers less than `n = 1`, so the answer is 0.

Constraints

  • 1 <= s.length <= 800
  • s has no leading zeros.
  • s consists only of the characters '0' and '1'.
  • 1 <= k <= 5

Solution

Method 1 – Digit DP with Set Bit Reduction

Intuition

A number is k-reducible if, after at most k operations of replacing it with the count of set bits in its binary representation, it becomes 1. We can use digit DP to count numbers less than n (given as a binary string) that are k-reducible.

Approach

  1. Precompute for each possible number of set bits, how many steps it takes to reduce to 1 (using the set bit count operation repeatedly).
  2. Use digit DP to count numbers less than n with a given number of set bits.
  3. For each possible set bit count, if it can be reduced to 1 in at most k steps, add the count to the answer.
  4. Return the answer modulo 1e9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

const int MOD = 1e9+7;
int steps[1005];
int popcount(int x) {
    int cnt = 0;
    while (x) { cnt += x & 1; x >>= 1; }
    return cnt;
}
void precompute() {
    steps[0] = -1; steps[1] = 0;
    for (int i = 2; i < 1005; ++i) steps[i] = steps[popcount(i)] + 1;
}
int dp[65][65][2];
int dfs(const string& s, int pos, int cnt, int tight) {
    if (pos == s.size()) return cnt;
    if (dp[pos][cnt][tight] != -1) return dp[pos][cnt][tight];
    int res = 0, up = tight ? s[pos]-'0' : 1;
    for (int d = 0; d <= up; ++d) {
        res = (res + dfs(s, pos+1, cnt+d, tight && d==up)) % MOD;
    }
    return dp[pos][cnt][tight] = res;
}
class Solution {
public:
    int countKReducibleNumbers(string s, int k) {
        precompute();
        int n = s.size(), ans = 0;
        for (int ones = 1; ones <= n*2; ++ones) {
            if (steps[ones] > k || steps[ones] == -1) continue;
            memset(dp, -1, sizeof dp);
            int cnt = dfs(s, 0, 0, 1);
            if (ones == 1) cnt = (cnt - 1 + MOD) % MOD;
            ans = (ans + cnt) % MOD;
        }
        return ans;
    }
};
1

// Not practical for Go due to recursion and memoization limits, see C++/Python.
1

// Not practical for Java due to recursion and memoization limits, see C++/Python.
1

// Not practical for Kotlin due to recursion and memoization limits, see C++/Python.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

MOD = 10**9+7
from functools import lru_cache

def popcount(x: int) -> int:
    return bin(x).count('1')

def precompute(maxn: int = 1005):
    steps = [-1] * maxn
    steps[0] = -1
    steps[1] = 0
    for i in range(2, maxn):
        steps[i] = steps[popcount(i)] + 1
    return steps

class Solution:
    def countKReducibleNumbers(self, s: str, k: int) -> int:
        steps = precompute(len(s)*2+5)
        n = len(s)
        @lru_cache(None)
        def dfs(pos: int, cnt: int, tight: int) -> int:
            if pos == n:
                return int(cnt)
            res = 0
            up = int(s[pos]) if tight else 1
            for d in range(up+1):
                res = (res + dfs(pos+1, cnt+d, tight and d==up)) % MOD
            return res
        ans = 0
        for ones in range(1, n*2+1):
            if steps[ones] > k or steps[ones] == -1:
                continue
            cnt = dfs(0, 0, 1)
            if ones == 1:
                cnt = (cnt - 1 + MOD) % MOD
            ans = (ans + cnt) % MOD
        return ans
1

// Not practical for Rust due to recursion and memoization limits, see C++/Python.

1

// Not practical for TypeScript due to recursion and memoization limits, see C++/Python.

Complexity

  • ⏰ Time complexity: O(n^2), where n is the length of the binary string, due to digit DP and precomputation.
  • 🧺 Space complexity: O(n^2), for memoization and DP arrays.