# Count K-Reducible Numbers Less Than N
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-k-reducible-numbers-less-than-n)
Canonical: https://scaleengineer.com/dsa/problems/count-k-reducible-numbers-less-than-n
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
**Data structures:** String
---
## 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** `109 + 7`.

**Example 1:**

**Input:** s = "111", k = 1

**Output:** 3

**Explanation:** 

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

**Example 2:**

**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:**

**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`

# Approaches
## Digit DP without Precomputation
This approach uses digit dynamic programming to count the numbers without iterating through all numbers up to `n`, which is infeasible given the constraints. The core idea is to build the binary representation of numbers digit by digit and count how many valid numbers can be formed. The validity check (whether a number is k-reducible) is performed on-the-fly within the recursion's base case. This method is conceptually simpler but less performant due to repeated calculations.
**Time:** O(L^2 * k * log L), where L is the length of `s`. The DP has `O(L^2)` states. The transition is O(1), but the base case involves a call to `is_p_reducible`, which takes `O(k * log L)` time as `popcount` is applied `k-1` times on values up to `L`. · **Space:** O(L^2) for the memoization table.
**Pros:** Relatively simple to implement as it avoids complex precomputation logic.; Uses less memory compared to the precomputation approach as it doesn't need an extra table for target popcounts.
**Cons:** Less efficient due to redundant computations. The `is_p_reducible` function is called many times for the same popcount values.; The time complexity has a factor of `k`, making it slower for larger `k`.
### Explanation
The solution revolves around a recursive function, let's call it `solve(index, pop_count, is_less)`, which counts the number of k-reducible integers that can be formed from a given state.

1.  **State Definition:**
    *   `index`: The current bit position (from left, 0-indexed) we are filling.
    *   `pop_count`: The number of set bits ('1's) in the prefix of the number constructed so far.
    *   `is_less`: A boolean flag that is true if the prefix we have built is already smaller than the corresponding prefix of `n` (given by string `s`).

2.  **k-Reducibility Check:** A number `x` is k-reducible if and only if its popcount, `p = popcount(x)`, is `(k-1)`-reducible. A helper function `is_p_reducible(p, j)` is created to check this. It works by applying the `popcount` operation `j` times to `p` and checking if the final result is 1.

3.  **Recursion and Base Case:**
    *   The recursion explores placing a '0' or a '1' at the current `index`. The upper bound for the digit is '1' if `is_less` is true (we can use any digit), or `s[index]` if `is_less` is false (we are restricted to match `n`'s prefix).
    *   The base case for the recursion is when `index == s.length()`. At this point, a full number has been formed. We check if its `pop_count` makes it `k-reducible`. That is, we call `is_p_reducible(current_popcount, k-1)`. If it is, we have found one valid number and return 1; otherwise, we return 0.

4.  **Memoization:** To avoid recomputing results for the same state `(index, pop_count, is_less)`, we use a 3D array `memo` to store the results.

5.  **Final Calculation:** The initial call is `solve(0, 0, false)`. This counts all k-reducible numbers in `[0, n]`. Since we need to count positive integers strictly less than `n`, we must subtract 1 from the total if `n` itself is k-reducible. The number 0 has a popcount of 0, which is never reducible, so it's correctly excluded.

```java
import java.util.Arrays;

class Solution {
    private long[][][] memo;
    private String s;
    private int n;
    private int k;
    private static final int MOD = 1_000_000_007;

    private boolean isPReducible(int p, int j) {
        if (p <= 0) return false;
        if (j < 0) return false;
        int currentVal = p;
        for (int i = 0; i < j; i++) {
            currentVal = Integer.bitCount(currentVal);
        }
        return currentVal == 1;
    }

    public int countKReducible(String s, int k) {
        this.s = s;
        this.n = s.length();
        this.k = k;
        
        this.memo = new long[n][n + 1][2];
        for (long[][] arr2D : memo) {
            for (long[] arr1D : arr2D) {
                Arrays.fill(arr1D, -1);
            }
        }

        long totalCount = solve(0, 0, false);

        int popcountN = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') popcountN++;
        }
        
        if (isPReducible(popcountN, k - 1)) {
            totalCount = (totalCount - 1 + MOD) % MOD;
        }

        return (int) totalCount;
    }

    private long solve(int idx, int count, boolean isLess) {
        if (idx == n) {
            return isPReducible(count, k - 1) ? 1 : 0;
        }
        if (memo[idx][count][isLess ? 1 : 0] != -1) {
            return memo[idx][count][isLess ? 1 : 0];
        }

        long ans = 0;
        int upperBound = isLess ? 1 : s.charAt(idx) - '0';

        for (int digit = 0; digit <= upperBound; digit++) {
            boolean newIsLess = isLess || (digit < upperBound);
            ans = (ans + solve(idx + 1, count + digit, newIsLess)) % MOD;
        }

        return memo[idx][count][isLess ? 1 : 0] = ans;
    }
}
```
### Algorithm
- Define a helper function `is_p_reducible(p, j)` that checks if a number `p` is `j`-reducible by applying `popcount` `j` times.
- Define a memoized recursive function `solve(index, pop_count, less)`.
- The state of the recursion is defined by the current bit `index`, the `pop_count` of the prefix, and a boolean `is_less` indicating if the number is already smaller than `n`'s prefix.
- The base case for the recursion is `index == s.length()`. Here, check if the final `pop_count` is `(k-1)`-reducible using the helper function. Return 1 if it is, 0 otherwise.
- In the recursive step, iterate through possible digits ('0' or '1') for the current `index` and make recursive calls for `index + 1` with updated parameters.
- The initial call is `solve(0, 0, false)`.
- The result counts k-reducible numbers in `[0, n]`. Subtract 1 if `n` itself is k-reducible to get the final answer for numbers `< n`.

## Digit DP with Precomputation
This is the most efficient approach, building upon the digit DP strategy. It significantly improves performance by precomputing all the necessary information before starting the DP process. Specifically, we precompute which popcount values result in a k-reducible number. This turns the expensive check in the DP's base case into a simple O(1) lookup.
**Time:** O(L^2 + k*L), where L is the length of `s`. The precomputation of target popcounts takes `O(k*L)`. The digit DP part has `O(L^2)` states, and each transition takes `O(1)` time. The total time is dominated by the DP, so it's effectively `O(L^2)`. · **Space:** O(L^2 + k*L). `O(L^2)` for the memoization table and `O(k*L)` for the reducibility precomputation table (can be optimized to `O(L)`).
**Pros:** Highly efficient, with a time complexity independent of `k` for the DP part.; The expensive reducibility check is factored out into a single precomputation step.; Optimal solution for the given constraints.
**Cons:** More complex to implement due to the initial precomputation phase.; Requires additional space for the precomputation table (`O(k*L)`).
### Explanation
This optimized solution consists of two main phases: precomputation and digit DP.

1.  **Precomputation of Target Popcounts:**
    The key insight is that a number `x` is `k-reducible` if and only if its `popcount(x)` is `(k-1)`-reducible. The numbers we are counting are less than `n`, so their popcount is at most `L = s.length()`. We can determine all popcount values `p 
in [1, L]` that are `(k-1)`-reducible.
    We can use dynamic programming for this precomputation. Let `is_reducible[j][p]` be a boolean indicating if `p` is `j`-reducible.
    *   Base case: `is_reducible[0][p]` is true only for `p=1`.
    *   Transition: `is_reducible[j][p]` is true if `is_reducible[j-1][popcount(p)]` is true.
    We compute this table for `j` from 1 to `k-1`. The set of target popcounts, `T`, will be all `p` for which `is_reducible[k-1][p]` is true.

2.  **Digit DP with Memoization:**
    With the target popcounts precomputed in a boolean array `targetPopcounts`, the digit DP structure is the same as the previous approach. We use a recursive function `solve(index, pop_count, is_less)` with the same state definition and memoization.
    The crucial difference is in the base case (`index == s.length()`). Instead of calling a helper function, we simply check `targetPopcounts[pop_count]`. This is an `O(1)` lookup.

3.  **Final Calculation:**
    The main logic remains the same. We call `solve(0, 0, false)` to get the count of k-reducible numbers in `[0, n]`. Then, we subtract 1 if `n` itself is k-reducible (i.e., if `popcount(n)` is in our precomputed set of target popcounts).

```java
import java.util.Arrays;

class Solution {
    private long[][][] memo;
    private String s;
    private boolean[] targetPopcounts;
    private int n;
    private static final int MOD = 1_000_000_007;

    public int countKReducible(String s, int k) {
        this.s = s;
        this.n = s.length();
        
        // Step 1: Precompute target popcounts
        this.targetPopcounts = new boolean[n + 1];
        if (k > 0) {
            boolean[] isPReducible = new boolean[n + 1];
            isPReducible[1] = true; // 1 is 0-reducible
            
            for (int j = 1; j < k; j++) {
                boolean[] nextIsPReducible = new boolean[n + 1];
                for (int p = 1; p <= n; p++) {
                    int pop = Integer.bitCount(p);
                    if (pop <= n && isPReducible[pop]) {
                        nextIsPReducible[p] = true;
                    }
                }
                isPReducible = nextIsPReducible;
            }
            this.targetPopcounts = isPReducible;
        }

        // Step 2: DP with memoization
        this.memo = new long[n][n + 1][2];
        for (long[][] arr2D : memo) {
            for (long[] arr1D : arr2D) {
                Arrays.fill(arr1D, -1);
            }
        }

        long totalCount = solve(0, 0, false);

        int popcountN = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') {
                popcountN++;
            }
        }
        if (popcountN > 0 && targetPopcounts[popcountN]) {
            totalCount = (totalCount - 1 + MOD) % MOD;
        }

        return (int) totalCount;
    }

    private long solve(int idx, int count, boolean isLess) {
        if (idx == n) {
            return (count > 0 && targetPopcounts[count]) ? 1 : 0;
        }
        if (memo[idx][count][isLess ? 1 : 0] != -1) {
            return memo[idx][count][isLess ? 1 : 0];
        }

        long ans = 0;
        int upperBound = isLess ? 1 : s.charAt(idx) - '0';

        for (int digit = 0; digit <= upperBound; digit++) {
            boolean newIsLess = isLess || (digit < upperBound);
            ans = (ans + solve(idx + 1, count + digit, newIsLess)) % MOD;
        }

        return memo[idx][count][isLess ? 1 : 0] = ans;
    }
}
```
### Algorithm
- Precompute the set of target popcounts. A popcount `p` is a target if `p` is `(k-1)`-reducible.
- This can be done with a DP table `is_reducible[j][p]`, where `is_reducible[j][p]` is true if `p` is `j`-reducible.
- The base case is `is_reducible[0][1] = true`.
- The transition is `is_reducible[j][p] = is_reducible[j-1][popcount(p)]`.
- Store the final `is_reducible[k-1]` array as the `targetPopcounts` lookup table.
- Use the same memoized recursive function `solve(index, pop_count, is_less)` as in the less efficient approach.
- In the base case (`index == s.length()`), perform an `O(1)` lookup in the `targetPopcounts` table to check validity.
- The final result is obtained by calling `solve(0, 0, false)` and adjusting for `n` itself.