Count K-Reducible Numbers Less Than N

Ah, the classic problem of counting K-reducible numbers less than N. In this problem, we’re tasked with finding how many positive integers less than a given number N can be reduced to zero using a specific number of operations, K.

Imagine you have a magical number that can only be reduced to zero if you perform a certain number of operations. It’s like trying to convince your friend to stop binge-watching their favorite show after just one episode. Good luck with that!

Solution Links

If you’re interested in seeing how this problem is tackled in other programming languages, check out the links below:

Code Solution


class Solution:
    def countKReducibleNumbers(self, s: str, k: int) -> int:
        kMod = 1_000_000_007
        ops = self._getOps(s)

        @functools.lru_cache(None)
        def dp(i: int, setBits: int, isTight: bool) -> int:
            if i == len(s):
                return int(ops[setBits] < k and not isTight)

            res = 0
            maxDigit = int(s[i]) if isTight else 1

            for d in range(maxDigit + 1):
                nextIsTight = isTight and (d == maxDigit)
                res += dp(i + 1, setBits + d, nextIsTight)
                res %= kMod
            return res

        return dp(0, 0, True) - 1  # - 0

    def _getOps(self, s: str) -> int:
        ops = [0] * (len(s) + 1)
        for num in range(2, len(s) + 1):
            ops[num] = 1 + ops[num.bit_count()]
        return ops

Approach Explanation

The solution employs a dynamic programming approach with memoization to efficiently count the K-reducible numbers. The function dp recursively explores each digit of the number, keeping track of the number of set bits and whether the current number is tightly bound to the original number. The helper function _getOps calculates the number of operations required to reduce a number to zero based on its bit count.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n * k), where n is the number of digits in the number and k is the maximum number of operations.
Space Complexity	O(n), due to the memoization cache storing results for each digit and set bit combination.

Real-World Example

Let’s say you’re trying to reduce your daily caffeine intake to zero. You start with a large cup of coffee (N) and decide that you can only have K sips before you feel jittery. Each sip represents an operation that reduces your caffeine level. The challenge is to figure out how many different ways you can sip your coffee (or avoid it altogether) while still adhering to your K limit.