2827. Number of Beautiful Integers in the Range LeetCode Solution
In this guide, you will get 2827. Number of Beautiful Integers in the Range LeetCode Solution with the best time and space complexity. The solution to Number of Beautiful Integers in the Range 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 Number of Beautiful Integers in the Range
You are given positive integers low, high, and k.
A number is beautiful if it meets both of the following conditions:
The count of even digits in the number is equal to the count of odd digits.
The number is divisible by k.
Return the number of beautiful integers in the range [low, high].
Example 1:
Input: low = 10, high = 20, k = 3
Output: 2
Explanation: There are 2 beautiful integers in the given range: [12,18].
– 12 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
– 18 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
Additionally we can see that:
– 16 is not beautiful because it is not divisible by k = 3.
– 15 is not beautiful because it does not contain equal counts even and odd digits.
It can be shown that there are only 2 beautiful integers in the given range.
Input: low = 1, high = 10, k = 1
Output: 1
Explanation: There is 1 beautiful integer in the given range: [10].
– 10 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 1.
It can be shown that there is only 1 beautiful integer in the given range.
Example 3:
Input: low = 5, high = 5, k = 2
Output: 0
Explanation: There are 0 beautiful integers in the given range.
– 5 is not beautiful because it is not divisible by k = 2 and it does not contain equal even and odd digits.
Constraints:
0 < low <= high <= 109
0 < k <= 20
Complexity Analysis
Time Complexity: O(|\texttt{high}| \cdot 10^2 \cdot k \cdot 2^2 \cdot 10)
Space Complexity: O(|\texttt{high}| \cdot 10^2 \cdot k \cdot 2^2)
2827. Number of Beautiful Integers in the Range LeetCode Solution in C++
class Solution {
public:
int numberOfBeautifulIntegers(int low, int high, int k) {
const string lowString = to_string(low);
const string highString = to_string(high);
const string lowWithLeadingZeros =
string(highString.length() - lowString.length(), '0') + lowString;
vector<vector<vector<vector<vector<vector<int>>>>>> mem(
highString.length(),
vector<vector<vector<vector<vector<int>>>>>(
, vector<vector<vector<vector<int>>>>(
, vector<vector<vector<int>>>(
k, vector<vector<int>>(2, vector<int>(2, -1))))));
return count(lowWithLeadingZeros, highString, k, 0, 0, 0, 0, true, true,
true, mem);
}
private:
// Returns the number of beautiful integers, considering the i-th digit with
// counts of even `even` digits and odd `odd` digits, where the current number
// modulo k equals remainder, `isTight1` indicates if the current digit is
// tightly bound for `low` and `isTight2` indicates if the current digit is
// tightly bound for `high`
int count(const string& low, const string& high, int k, int i, int even,
int odd, int remainder, bool isLeadingZero, bool isTight1,
bool isTight2,
vector<vector<vector<vector<vector<vector<int>>>>>>& mem) {
if (i == high.length())
return !isLeadingZero && even == odd && remainder == 0;
if (mem[i][even][odd][remainder][isTight1][isTight2] != -1)
return mem[i][even][odd][remainder][isTight1][isTight2];
int res = 0;
const int minDigit = isTight1 ? low[i] - '0' : 0;
const int maxDigit = isTight2 ? high[i] - '0' : 9;
for (int d = minDigit; d <= maxDigit; ++d) {
const int nextEven = even + ((!isLeadingZero || d > 0) && d % 2 == 0);
const int nextOdd = odd + (d % 2 == 1);
const int nextRemainder = (remainder * 10 + d) % k;
const bool nextIsTight1 = isTight1 && (d == minDigit);
const bool nextIsTight2 = isTight2 && (d == maxDigit);
res += count(low, high, k, i + 1, nextEven, nextOdd, nextRemainder,
isLeadingZero && d == 0, nextIsTight1, nextIsTight2, mem);
}
return mem[i][even][odd][remainder][isTight1][isTight2] = res;
}
}; /* code provided by PROGIEZ */
2827. Number of Beautiful Integers in the Range LeetCode Solution in Java
N/A // code provided by PROGIEZ
2827. Number of Beautiful Integers in the Range LeetCode Solution in Python
