Count K-Reducible Numbers Less Than N - Solution & Explanation
Problem Statement
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
xwith 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 <= 800shas no leading zeros.sconsists only of the characters'0'and'1'.1 <= k <= 5
Approach Overview
Problem 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.
Approach 1: Brute Force Simulation
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.
Code
Python
Complexity
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.
Approach 2: Dynamic Programming Approach
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.
Code
Python
Complexity
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.
Approach 3: Approach 1: Dynamic Programming to Count K-Reducible Numbers
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.
Code
Python
JavaScript
Complexity
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.
Approach 4: Approach 2: Iterative Constraint Based Counting
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.
Complexity
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.
Complexity Comparison
| 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). |
Detailed Complexity Analysis
| 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 |
Video Solution
3352. Count K-Reducible Numbers Less Than N | Digit DP + 1D DP • Aryan Mittal • 1,835 views views
Watch 3 more video solutions →Frequently Asked Questions
Is Count K-Reducible Numbers Less Than N easy or hard?
Count K-Reducible Numbers Less Than N Python/Java solution
How to solve Count K-Reducible Numbers Less Than N in O(n)?
What is the best approach for Count K-Reducible Numbers Less Than N?
Is Count K-Reducible Numbers Less Than N asked at Google/Amazon/Meta?
What data structure is used in Count K-Reducible Numbers Less Than N?
What is the time complexity of Count K-Reducible Numbers Less Than N?
Ready to solve this problem?
Practice Count K-Reducible Numbers Less Than N with our built-in code editor and test cases.
Practice on FleetCode