LeetCode 3352 - Count K-Reducible Numbers Less Than N

Difficulty: 🔴 Hard
Topics: Math, String, Dynamic Programming, Combinatorics

Solution

Problem Understanding

The problem asks us to count the number of positive integers less than n (where n is given in binary as a string s) that are k-reducible. An integer x is k-reducible if applying the operation "replace x with the count of set bits in its binary representation" at most k times eventually reduces x to 1.

For example, consider x = 6 (binary "110"). The count of set bits is 2. Applying the operation again on 2 (binary "10") reduces it to 1. Therefore, 6 is 2-reducible but not 1-reducible.

The input s is a binary string representing a number n that can be up to 800 bits long, which implies n can be very large (~10^240), far exceeding what brute force integer iteration can handle. The integer k is small (1 <= k <= 5). The output should be the count modulo 10^9 + 7.

Edge cases include the smallest inputs (s = "1"), very large s, and cases where k is minimal or maximal. Naive iteration over all numbers < n is infeasible due to the size of n.

Approaches

Brute Force

A brute-force approach would iterate through all integers from 1 to n-1, repeatedly count set bits up to k times, and check if the number reduces to 1. While correct for small numbers, it is infeasible here because n can have up to 800 bits. Iterating up to numbers as large as 2^800 is computationally impossible.

Optimal Approach

The key insight is that the number of steps to reduce any number to 1 via set-bit counting is small and can be precomputed for small numbers (1 <= x <= 800) because x reduces rapidly under repeated set-bit counting. This allows us to convert the problem into a digit dynamic programming problem over the binary representation of n.

We define a function f(x) to count the number of reductions required to reach 1. Using combinatorics, we can compute the number of numbers less than n with exactly c set bits, for all c that satisfy f(c) <= k-1. By iterating through all possible numbers of set bits and applying Pascal's triangle combinatorial calculations, we can compute the total count without enumerating all integers.

This combines precomputation of reduction steps and binary digit DP with combinations, making it feasible even for s with length up to 800.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * k)	O(1)	Iterate all numbers and reduce; infeasible for large `n`
Optimal	O(L^2 + k*L)	O(L + k)	L = length of `s`; uses precomputed reductions and combinatorics

Algorithm Walkthrough

Precompute Reduction Steps: For all integers x from 1 to 800, repeatedly apply the "count set bits" operation until reaching 1. Store the number of steps in an array steps[x].
Count k-reducible set-bit counts: Identify all integers c such that steps[c] <= k-1. These counts correspond to numbers that can become 1 in at most k reductions.
Digit DP over binary string s: We iterate over each bit of s, maintaining the count of set bits selected so far. Use combinatorial calculations to compute how many numbers with exactly c set bits exist that are less than n.
Sum counts for valid c: For each c in the precomputed valid counts, compute the combination of positions to place c set bits and sum the totals modulo 10^9 + 7.
Handle edge cases: Subtract 1 if necessary to avoid counting 0 as a valid number.

Why it works: The combination of precomputing reduction steps and counting numbers by set-bit counts guarantees that all numbers counted can be reduced to 1 within k operations. The digit DP ensures we only count numbers less than n.

Python Solution

class Solution:
    MOD = 10**9 + 7
    
    def countKReducibleNumbers(self, s: str, k: int) -> int:
        if s == "1":
            return 0
        
        # Precompute steps to reduce x to 1
        max_len = 801
        steps = [0] * max_len
        steps[1] = 0
        for i in range(2, max_len):
            steps[i] = steps[bin(i).count('1')] + 1
        
        # Precompute valid set-bit counts
        valid_counts = [i for i in range(1, max_len) if steps[i] <= k-1]
        
        # Precompute combinations (Pascal's triangle)
        n_bits = len(s)
        comb = [[0]*(n_bits+1) for _ in range(n_bits+1)]
        for i in range(n_bits+1):
            comb[i][0] = 1
            for j in range(1, i+1):
                comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % self.MOD
        
        res = 0
        set_bits = 0
        for i, ch in enumerate(s):
            if ch == '1':
                remaining = len(s) - i - 1
                for c in valid_counts:
                    if c - set_bits >= 0 and c - set_bits <= remaining:
                        res = (res + comb[remaining][c - set_bits]) % self.MOD
                set_bits += 1
        
        if steps[set_bits] <= k-1:
            res = (res + 1) % self.MOD
        
        return (res - 1) % self.MOD

Explanation: The solution first precomputes how many operations each number takes to reduce to 1. Then it identifies all set-bit counts that are k-reducible. Using digit DP, it iterates through s and counts all numbers less than n with valid set-bit counts, leveraging precomputed combinatorial values.

Go Solution

package main

func countKReducibleNumbers(s string, k int) int {
    MOD := 1000000007
    if s == "1" {
        return 0
    }

    maxLen := 801
    steps := make([]int, maxLen)
    steps[1] = 0
    for i := 2; i < maxLen; i++ {
        steps[i] = steps[bitCount(i)] + 1
    }

    validCounts := []int{}
    for i := 1; i < maxLen; i++ {
        if steps[i] <= k-1 {
            validCounts = append(validCounts, i)
        }
    }

    nBits := len(s)
    comb := make([][]int, nBits+1)
    for i := 0; i <= nBits; i++ {
        comb[i] = make([]int, nBits+1)
        comb[i][0] = 1
        for j := 1; j <= i; j++ {
            comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD
        }
    }

    res := 0
    setBits := 0
    for i, ch := range s {
        if ch == '1' {
            remaining := nBits - i - 1
            for _, c := range validCounts {
                if c-setBits >= 0 && c-setBits <= remaining {
                    res = (res + comb[remaining][c-setBits]) % MOD
                }
            }
            setBits++
        }
    }

    if steps[setBits] <= k-1 {
        res = (res + 1) % MOD
    }

    return (res - 1 + MOD) % MOD
}

func bitCount(x int) int {
    count := 0
    for x > 0 {
        count += x & 1
        x >>= 1
    }
    return count
}

Explanation: The Go version mirrors the Python solution. It uses slices for combinatorial calculations and precomputes the number of steps using a helper bitCount function. Edge cases and modular arithmetic are handled similarly.

Worked Examples

Example 1: s = "111", k = 1

Binary length = 3. Valid set-bit counts for k=1 are [1]. Using combinations, numbers with 1 set bit less than 7 are 1, 2, 4. Answer = 3.

Example 2: s = "1000", k = 2

Binary length = 4. Valid counts for k=2 are [1,2]. Combinations yield numbers with 1 or 2 set bits less than 8: 1,2,3,4,5,6. Answer = 6.

Example 3: s = "1", k = 3