Count K-Reducible Numbers Less Than N

Ah, the classic problem of counting K-reducible numbers less than N. You know, it’s like trying to count how many times you’ve said “I’ll start my diet tomorrow” while staring at a pizza. Spoiler alert: it’s a lot! 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. Sounds simple, right? Well, buckle up, because it’s about to get a bit more complicated than your last relationship!

Problem Description

The problem is to count how many positive integers less than a given number N can be reduced to zero using at most K operations. Each operation consists of reducing the number by the count of its set bits (the number of 1s in its binary representation). So, if you thought counting calories was hard, try counting set bits!

Imagine you have a number like 5 (which is 101 in binary). It has two set bits. If you reduce it by 2, you get 3. Keep going until you hit zero, and you’ll see how many operations it takes. Now, do this for every number less than N and see how many of them can be reduced to zero in K operations.

Solution in Java


class Solution {
  public int countKReducibleNumbers(String s, int k) {
    Integer[][][] mem = new Integer[s.length()][s.length() + 1][2];
    return count(s, 0, 0, true, k, getOps(s), mem) - 1; // - 0
  }

  private static final int kMod = 1_000_000_007;

  private int count(String s, int i, int setBits, boolean isTight, int k, int[] ops,
                    Integer[][][] mem) {
    if (i == s.length())
      return (ops[setBits] < k && !isTight) ? 1 : 0;
    if (mem[i][setBits][isTight ? 1 : 0] != null)
      return mem[i][setBits][isTight ? 1 : 0];

    int res = 0;
    final int maxDigit = isTight ? s.charAt(i) - '0' : 1;

    for (int d = 0; d <= maxDigit; ++d) {
      final boolean nextIsTight = isTight && (d == maxDigit);
      res += count(s, i + 1, setBits + d, nextIsTight, k, ops, mem);
      res %= kMod;
    }

    return mem[i][setBits][isTight ? 1 : 0] = res;
  }

  private int[] getOps(String s) {
    int[] ops = new int[s.length() + 1];
    for (int num = 2; num <= s.length(); ++num)
      ops[num] = 1 + ops[Integer.bitCount(num)];
    return ops;
  }
}

Approach Explanation

The approach used in the code is a dynamic programming technique combined with a recursive function. The function count explores all possible numbers less than N by iterating through each digit and checking how many set bits are present. It uses memoization to store results of previously computed states to avoid redundant calculations. The getOps function calculates the number of operations required to reduce each number to zero based on its set bits.

Time and Space Complexity

Time Complexity: O(n^2), where n is the length of the string representation of N. This is due to the recursive exploration of digits and the memoization.
Space Complexity: O(n^2) as well, for storing the memoization table.

Real-World Example

Let’s say you’re trying to count how many times you can eat pizza before you hit your calorie limit (which is N). Each slice of pizza has a certain number of calories (like the set bits in a number). You can only eat a certain number of slices (operations) before you have to stop. This problem is like figuring out how many combinations of slices you can eat without exceeding your calorie limit.