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:
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 <= 800s has no leading zeros.s consists only of the characters '0' and '1'.1 <= k <= 5Problem Overview: Given a binary string N, count how many positive integers strictly less than N become 1 after applying the operation x = popcount(x) at most k times. A number is k-reducible if repeatedly replacing it with the number of set bits eventually reaches 1 within k steps.
Approach 1: Brute Force Simulation (O(N log N) time, O(1) space)
Iterate through every integer x from 1 to N-1. For each value, repeatedly compute popcount(x) until the number becomes 1 or the step count exceeds k. This directly simulates the definition of k-reducibility. The method is easy to reason about but completely impractical when N is large (often up to hundreds of bits). It mainly helps verify correctness on small inputs and understand the reduction process.
Approach 2: Dynamic Programming Simulation (O(L * log L) time, O(L) space)
Instead of simulating the full value of each number, focus on the number of set bits. Any integer eventually reduces to a small sequence determined by its initial popcount. Precompute how many steps each possible bit count requires to reach 1. For numbers with binary length L, the maximum popcount is L, so you can precompute reductions for all counts from 1..L. Then count numbers below N with a valid bit count using digit-style iteration over the binary string. This combines dynamic programming with bit counting.
Approach 3: Dynamic Programming to Count K-Reducible Numbers (O(L^2) time, O(L^2) space)
The optimal approach treats the problem as a binary digit DP. Traverse the bits of N from left to right and track how many 1s have been chosen so far. For every prefix that becomes smaller than N, count combinations of remaining bits using C(n, r). Each candidate total bit count is checked against the precomputed reduction steps to see if it reaches 1 within k. This works because the reduction path depends only on the number of set bits, not the original value. The method relies heavily on combinatorics and dynamic programming.
Approach 4: Iterative Constraint Based Counting (O(L^2) time, O(L) space)
Another implementation uses the same key observation but performs counting iteratively. While scanning the binary digits of N, when encountering a 1, temporarily flip it to 0 and count all numbers formed by the remaining suffix with a chosen number of set bits. Combination formulas determine how many such numbers exist. Each possible final bit count is validated against the precomputed step requirement. This approach avoids a full DP table and keeps memory small while still leveraging math and combinatorial counting.
Recommended for interviews: The combinatorics + digit DP approach is the expected solution. Interviewers want to see the key insight that the reduction chain depends only on the number of set bits. Brute force demonstrates understanding of the process, but the optimized counting approach shows strong skills with binary digit DP and combinatorial reasoning.
This approach involves simulating the reduction process for every integer less than n. By counting set bits repeatedly, we check if the number of operations required to reduce a number x to 1 is less than or equal to k.
First, convert the binary string to an integer. For every number less than n, count the number of times we need to convert it to the set bits count, considering the operation should not exceed k times. If the number becomes 1 during this process, consider it as a valid k-reducible number. Finally, use modulo operation to control large outputs.
Python
Time Complexity: O(N * k) where N is the value of n derived from the binary string.
Space Complexity: O(1), as we're only using a fixed amount of extra space.
This approach uses dynamic programming to optimize counting of k-reducible numbers. Create a table that keeps track of counts of each popcount value resulting from every operation step, propagating counts appropriately.
We maintain a 2D dp table where dp[x][j] tracks how many times number x can be reached with exactly j reductions from any number less than n. Update the table iteratively while propagating possible reductions using the popcount and maintain a running sum for valid k-reducible numbers.
Python
Time Complexity: O(N * k) where N is derived from the binary string n.
Space Complexity: O(Nk), where we store results of subproblems in a 2D array.
This approach uses dynamic programming to count how many k-reducible numbers exist. The problem revolves around counting the operations required to reduce each integer to 1. Imagine that we record each state and whether we can achieve 1 with k reductions. By moving backwards from n, this prevents unnecessary recalculations.
This Python function calculates the number of k-reducible numbers less than a given n. We use dynamic programming to build solutions for smaller sub-problems and combine them to find the result, using modulo operations to avoid overflow. We maintain a 2D dp table where cells store boolean values determining if a number is k-reducible. You need to parse the integer before processing.
Python
JavaScript
Time Complexity: O(n * k) where n is the integer form of the binary input and k is given.
Space Complexity: O(n * k) for the dp table.
Instead of calculating the reducibility of each number, observe the operations and number constraints. By mapping the state transitions manually with constraints, we can iterate over possible values and directly count the numbers.
This C code iteratively checks numbers less than n to see if they are k-reducible. It computes the set bits count and counts the operations manually, without storing intermediate results. The resulting count is taken modulo 10^9+7 to prevent overflow issues.
Time Complexity: Depends on the average number of set bit counts per number. In the worst case, it's O(n * log n).
Space Complexity: O(1) as there's no additional data storage beyond the basic iteration needs.
| Approach | Complexity |
|---|---|
| Brute Force Simulation | Time Complexity: O(N * k) where N is the value of n derived from the binary string. |
| Dynamic Programming Approach | Time Complexity: O(N * k) where N is derived from the binary string n. |
| Approach 1: Dynamic Programming to Count K-Reducible Numbers | Time Complexity: O(n * k) where n is the integer form of the binary input and k is given. |
| Approach 2: Iterative Constraint Based Counting | Time Complexity: Depends on the average number of set bit counts per number. In the worst case, it's O(n * log n). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(N log N) | O(1) | Small N or validating logic of the reduction process |
| Dynamic Programming Simulation | O(L log L) | O(L) | When focusing on bit counts instead of full numbers |
| Digit DP + Combinatorics | O(L^2) | O(L^2) | General optimal solution for large binary N |
| Iterative Constraint Counting | O(L^2) | O(L) | Memory constrained implementations using combinatorics |
3352. Count K-Reducible Numbers Less Than N | Digit DP + 1D DP • Aryan Mittal • 1,787 views views
Watch 2 more video solutions →Practice Count K-Reducible Numbers Less Than N with our built-in code editor and test cases.
Practice on FleetCode