LeetCode Solutions Blog

Count K-Reducible Numbers Less Than N

Number: 3631

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a binary string s representing an integer n and an integer k, count how many positive integers x (with 1 ≤ x < n) are k‑reducible. An integer x is defined as k‑reducible if applying the following operation at most k times reduces it to 1: • Replace x with the count of set bits in its binary representation. Return the count modulo 10^9+7.

Key Insights

The operation “popcount” dramatically reduces x. In fact, for any integer x, repeatedly applying popcount will reduce x to a small number.
Precompute a helper function F where F(1) = 0 and for any x > 1, F(x) = 1 + F(popcount(x)). Then for x > 1, f(x) = 1 + F(popcount(x)) and we require f(x) ≤ k.
Equivalently, for x > 1, we need F(popcount(x)) ≤ k - 1. (The special case x = 1 always qualifies if 1 is in the range.)
Because s can be very long (up to 800 bits), we count numbers x (1 ≤ x < n) by “how many ones” appear in their binary representation. Standard combinatorial methods let us count numbers below n with exactly r ones.
Handle k = 0 as a special case (only x = 1 qualifies).

Space and Time Complexity

Time Complexity: O(L^2) where L is the length of s (up to 800) due to computing combinations and iterating over the bit positions. Space Complexity: O(L^2) for storing the combinations table.

Solution

We first precompute F(x) for x in [1, L] (since a number below n can have at most L ones). Note that F(1)=0 and for x>1, F(x)=1+F(popcount(x)). Then, for every candidate x (which is determined by its popcount r), we want: – if x = 1, it always qualifies. – if x > 1, we require that 1 + F(r) ≤ k (or equivalently F(r) ≤ k-1). To count numbers x below n with exactly r ones, we use a combinatorial approach. Iterating over the bits of s, whenever we encounter a ‘1’ we add the number of ways to choose the remaining (r – onesSoFar) ones from the remaining positions. (Be sure to subtract one if the number exactly equals n, since we need x < n.) As a special case, if k is 0, only x = 1 qualifies provided 1 < n.

Code Solutions

MOD = 10**9 + 7

# Precompute combinations using Pascal's triangle up to n (choose table)
def precompute_combinations(n):
    comb = [[0]*(n+1) for _ in range(n+1)]
    for i in range(n+1):
        comb[i][0] = 1
        comb[i][i] = 1
        for j in range(1, i):
            comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD
    return comb

# Precompute minimal operations F(x) for x in [1, limit]
def precompute_F(limit):
    F = [-1] * (limit+1)
    F[1] = 0
    for x in range(2, limit+1):
        bits = bin(x).count("1")
        F[x] = 1 + F[bits]
    return F

# Count numbers less than n_str that have exactly 'ones' ones.
def count_with_ones(n_str, ones, comb):
    L = len(n_str)
    count = 0
    ones_so_far = 0
    for i in range(L):
        if n_str[i] == '1':
            remaining = L - i - 1
            if 0 <= ones - ones_so_far <= remaining:
                count = (count + comb[remaining][ones - ones_so_far]) % MOD
            ones_so_far += 1
    # If the number itself has exactly 'ones' ones, subtract it because we need strictly less than n.
    if ones_so_far == ones:
        count = (count - 1) % MOD
    return count

def count_k_reducible(s, k):
    L = len(s)
    # If n == "1", there are no numbers less than n.
    if s == "1":
        return 0
    
    comb = precompute_combinations(L + 10)
    F = precompute_F(L + 1)
    
    # Special-case k = 0: only x==1 qualifies.
    if k == 0:
        return 1 % MOD

    ans = 0
    # For each possible popcount r (r from 1 to L)
    for r in range(1, L+1):
        if r == 1:
            # For r==1, both x == 1 (cost 0) and other powers-of-two (cost 1) qualify if k>=1.
            cnt = count_with_ones(s, r, comb)
            ans = (ans + cnt) % MOD
        else:
            # For x > 1 with popcount r, condition is 1 + F(r) <= k <=> F(r) <= k-1.
            if F[r] <= k - 1:
                cnt = count_with_ones(s, r, comb)
                ans = (ans + cnt) % MOD
    # Add 1 explicitly for x = 1 (which might not be included by count_with_ones when s has length > 1).
    ans = (ans + 1) % MOD
    return ans

# Example usage:
if __name__ == "__main__":
    # Example 1: s = "111", k = 1 -> n = 7, valid numbers: 1, 2, 4 (3 numbers)
    print(count_k_reducible("111", 1))  # Expected output: 3

    # Example 2: s = "1000", k = 2 -> n = 8, valid numbers: 1,2,3,4,5,6 (6 numbers)
    print(count_k_reducible("1000", 2))  # Expected output: 6

    # Example 3: s = "1", k = 3 -> n = 1, so answer is 0
    print(count_k_reducible("1", 3))  # Expected output: 0