Count K-Reducible Numbers Less Than N solution and explanation
3 more videos on this problem
3352. Count K-Reducible Numbers Less Than N | Digit DP + 1D DPAryan Mittal · 25:55 · 1K views
3352. Count K-Reducible Numbers Less Than N (Leetcode Hard)Programming Live with Larry · 37:19 · 208 views
Leetcode Contest 423 | 3352. Count K-Reducible Numbers Less Than N | BIT DP | Today SolutionCode Wanderer · 15:27 · 60 views
Weekly Contest 423 | 3349, 3350, 3351 & 3352 | LeetcodeAmit Choraria · 49:57 · 52 views
The 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
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.
def k_reducible_count(s, k):
MOD = 10**9 + 7
n = int(s, 2)
count = 0
def popcount(x):
return bin(x).count('1')
for i in range(1, n):
x = i
operations = 0
while x != 1 and operations < k:
x = popcount(x)
operations += 1
if x == 1:
count += 1
return count % MOD
# Example Usage
s = "111"
k = 1
print(k_reducible_count(s, k)) # Output: 3First, 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.
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.
def k_reducible_count(s, k):
MOD = 10**9 + 7
n = int(s, 2)
dp = [[0] * (k + 1) for _ in range(n)]
dp[0][0] = 1
for i in range(1, n):
popcnt = bin(i).count('1')
for j in range(k + 1):
dp[i][j] = dp[i - 1][j]
if j > 0:
dp[popcnt][j] = (dp[popcnt][j] + dp[i][j - 1]) % MOD
result = sum(dp[1][:]) % MOD
return result
# Example Usage
s = "111"
k = 1
print(k_reducible_count(s, k)) # Output: 3We 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.
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.
MOD = 10**9 + 7
def count_set_bits(x):
return bin(x).count('1')
def count_k_reducible(n, k):
dp = [[0 for _ in range(k + 1)] for _ in range(n)]
for i in range(1, n):
dp[i][0] = 1 if i == 1 else 0
for j in range(1, k + 1):
set_bits_count = count_set_bits(i)
if set_bits_count < n:
dp[i][j] = dp[set_bits_count][j - 1]
return sum(dp[i][k] for i in range(1, n)) % MOD
binary_input = "1000"
k = 2
n = int(binary_input, 2)
print(count_k_reducible(n, k))const MOD = 10**9 + 7;
const countSetBits = (x) => x.toString(2).split('1').length - 1;
const countKReducible = (n, k) => {
const dp = Array.from({ length: n }, () => Array(k + 1).fill(0));
for (let i = 1; i < n; i++) {
dp[i][0] = i === 1 ? 1 : 0;
for (let j = 1; j <= k; j++) {
const setBitsCount = countSetBits(i);
if (setBitsCount < n) {
dp[i][j] = dp[setBitsCount][j - 1];
}
}
}
return dp.reduce((acc, val) => acc + val[k], 0) % MOD;
};
const binaryInput = "1000";
const k = 2;
const n = parseInt(binaryInput, 2);
console.log(countKReducible(n, k));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.
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.
public class KReducible {
private static final int MOD = 1000000007;
public static int countSetBits(int n) {
return Integer.bitCount(n);
}
public static int countKReducible(int n, int k) {
int result = 0;
for (int i = 1; i < n; ++i) {
int x = i;
int operations = 0;
while (x > 1 && operations < k) {
x = countSetBits(x);
operations++;
}
if (x == 1) {
result = (result + 1) % MOD;
}
}
return result;
}
public static void main(String[] args) {
String binaryInput = "1000";
int k = 2;
int n = Integer.parseInt(binaryInput, 2);
System.out.println(countKReducible(n, k));
}
}#include <stdio.h>
#define MOD 1000000007
int countSetBits(int n) {
int count = 0;
while (n) {
count += n & 1;
n >>= 1;
}
return count;
}
int countKReducible(int n, int k) {
int result = 0;
for (int i = 1; i < n; ++i) {
int x = i;
int operations = 0;
while (x > 1 && operations < k) {
x = countSetBits(x);
operations++;
}
if (x == 1) {
result = (result + 1) % MOD;
}
}
return result;
}
int main() {
const char* s = "1000";
int k = 2;
int n = strtol(s, NULL, 2);
printf("%d\n", countKReducible(n, k));
return 0;
}This Java solution uses a similar approach as the C solution. It's an iterative approach without caching, checking k-reducibility for numbers less than n by counting the number of set bits repeatedly until the number is reduced to 1 or operations reach k.
Time Complexity: Like C, it is O(n * log n) in the theoretical worst case.
Space Complexity: O(1), leveraging Java's call stack but no external storage.
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: Like C, it is O(n * log n) in the theoretical worst case. |
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 |
Frequently asked questions
Is Count K-Reducible Numbers Less Than N easy or hard?
Count K-Reducible Numbers Less Than N is classified as a Hard problem. It requires recognizing that the reduction process depends only on the number of set bits and combining that insight with digit dynamic programming and combinatorics to count valid numbers efficiently.
Count K-Reducible Numbers Less Than N Python/Java solution
Python solutions usually implement digit DP with precomputed combination values and a small array storing reduction steps for each possible popcount. Java implementations follow the same logic but often use iterative combinatorics tables for efficiency. Both achieve O(L^2) time complexity.
How to solve Count K-Reducible Numbers Less Than N in O(n)?
A strict O(n) solution is generally not used because counting combinations of bit placements requires evaluating multiple possibilities for each prefix. The closest efficient solution is O(L^2) using digit DP and combinatorics, where L is the number of bits in N. It iterates through each bit position and evaluates possible counts of remaining set bits.
What is the best approach for Count K-Reducible Numbers Less Than N?
The best approach uses digit dynamic programming with combinatorics. Instead of checking every number, it counts how many numbers below N have a specific number of set bits. Since the reduction process only depends on the popcount, you precompute how many steps each bit count needs to reach 1 and sum the valid cases. This runs in O(L^2) time where L is the number of bits in N.
Is Count K-Reducible Numbers Less Than N asked at Google/Amazon/Meta?
Hard combinatorics and digit DP problems like this commonly appear in interviews at companies such as Google, Amazon, and Meta. The problem tests understanding of bit manipulation, combinatorial counting, and dynamic programming on digit constraints, which are common interview themes.
What data structure is used in Count K-Reducible Numbers Less Than N?
The solution primarily uses arrays for dynamic programming and combinatorics tables such as Pascal's triangle for computing combinations. The core technique is digit DP over the binary string combined with precomputed popcount reduction steps.
What is the time complexity of Count K-Reducible Numbers Less Than N?
The optimal digit DP and combinatorics solution runs in O(L^2) time and O(L^2) space, where L is the length of the binary representation of N. Precomputing reduction steps for bit counts takes O(L log L), and counting combinations during the binary traversal dominates the complexity.