Scale Engineer

Count K-Reducible Numbers Less Than N

Hard
#2978Time: 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.
Patterns
MathDynamic ProgrammingCombinatorics
Data structures
String

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem