3352. Count K-Reducible Numbers Less Than N LeetCode Solution
In this guide, you will get 3352. Count K-Reducible Numbers Less Than N LeetCode Solution with the best time and space complexity. The solution to Count K-Reducible Numbers Less Than N problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count K-Reducible Numbers Less Than N
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 x with 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.
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 <= 800
s has no leading zeros.
s consists only of the characters '0' and '1'.
1 <= k <= 5
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n)
3352. Count K-Reducible Numbers Less Than N LeetCode Solution in C++
class Solution {
public:
int countKReducibleNumbers(string s, int k) {
vector<vector<vector<int>>> mem(
s.length(), vector<vector<int>>(s.length() + 1, vector<int>(2, -1)));
return count(s, 0, 0, true, k, getOps(s), mem) - 1; // - 0
}
private:
static constexpr int kMod = 1'000'000'007;
// Returns the number of positive integers less than n that are k-reducible,
// considering the i-th digit, where `setBits` is the number of set bits in
// the current number, and `isTight` indicates if the current digit is
// tightly bound.
int count(const string& s, int i, int setBits, bool isTight, int k,
const vector<int>& ops, vector<vector<vector<int>>>& mem) {
if (i == s.length())
return (ops[setBits] < k && !isTight) ? 1 : 0;
if (mem[i][setBits][isTight] != -1)
return mem[i][setBits][isTight];
int res = 0;
const int maxDigit = isTight ? s[i] - '0' : 1;
for (int d = 0; d <= maxDigit; ++d) {
const bool nextIsTight = isTight && (d == maxDigit);
res += count(s, i + 1, setBits + d, nextIsTight, k, ops, mem);
res %= kMod;
}
return mem[i][setBits][isTight] = res;
};
// Returns the number of operations to reduce a number to 0.
vector<int> getOps(string& s) {
vector<int> ops(s.length() + 1);
for (int num = 2; num <= s.length(); ++num)
ops[num] = 1 + ops[__builtin_popcount(num)];
return ops;
}
}; /* code provided by PROGIEZ */
3352. Count K-Reducible Numbers Less Than N LeetCode 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;
// Returns the number of positive integers less than n that are k-reducible,
// considering the i-th digit, where `setBits` is the number of set bits in
// the current number, and `isTight` indicates if the current digit is
// tightly bound.
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;
}
// Returns the number of operations to reduce a number to 0.
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;
}
} // code provided by PROGIEZ
3352. Count K-Reducible Numbers Less Than N LeetCode Solution in Python
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:
"""
Returns the number of positive integers less than n that are k-reducible,
considering the i-th digit, where `setBits` is the number of set bits in
the current number, and `isTight` indicates if the current digit is
tightly bound.
"""
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:
"""Returns the number of operations to reduce a number to 0."""
ops = [0] * (len(s) + 1)
for num in range(2, len(s) + 1):
ops[num] = 1 + ops[num.bit_count()]
return ops # code by PROGIEZ
