Problem

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].

Examples

Example 1

1
2
3
4
5
6
7
8
9

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.

Example 2

1
2
3
4
5

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

1
2
3
4

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 <= 10^9
  • 0 < k <= 20

Solution

Method 1 – Digit DP (Dynamic Programming)

Intuition

Count numbers with equal even/odd digits and divisible by k using digit DP. For range [low, high], use f(high) - f(low-1).

Approach

  1. Define a DP: dp(pos, even, odd, mod, tight) = ways to build numbers up to bound.
  2. For each digit, update even/odd count, mod, and tight bound.
  3. Only count numbers with even == odd and mod == 0.
  4. Use memoization for efficiency.
  5. Compute for high and low-1, subtract.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    int k;
    int dp(int pos, int even, int odd, int mod, bool tight, const vector<int>& digits, vector<vector<vector<vector<vector<int>>>>>& memo) {
        if (pos == digits.size()) return even == odd && mod == 0;
        if (memo[pos][even][odd][mod][tight] != -1) return memo[pos][even][odd][mod][tight];
        int res = 0, up = tight ? digits[pos] : 9;
        for (int d = 0; d <= up; ++d) {
            int ne = even + (d%2==0);
            int no = odd + (d%2==1);
            res += dp(pos+1, ne, no, (mod*10+d)%k, tight && d==up, digits, memo);
        }
        return memo[pos][even][odd][mod][tight] = res;
    }
    int f(int x) {
        vector<int> digits;
        for (; x; x/=10) digits.push_back(x%10);
        reverse(digits.begin(), digits.end());
        int n = digits.size();
        vector<vector<vector<vector<vector<int>>>>> memo(n+1, vector<vector<vector<vector<int>>>>(n+1, vector<vector<vector<int>>>(n+1, vector<vector<int>>(k, vector<int>(2, -1)))));
        return dp(0,0,0,0,1,digits,memo);
    }
    int numberOfBeautifulIntegers(int low, int high, int K) {
        k = K;
        return f(high) - f(low-1);
    }
};
1

// Go implementation omitted for brevity (use digit DP as above)
1

// Java implementation omitted for brevity (use digit DP as above)
1

// Kotlin implementation omitted for brevity (use digit DP as above)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

from functools import lru_cache
class Solution:
    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:
        def f(x):
            s = str(x)
            n = len(s)
            @lru_cache(None)
            def dp(pos, even, odd, mod, tight):
                if pos == n:
                    return even == odd and mod == 0
                res = 0
                up = int(s[pos]) if tight else 9
                for d in range(0, up+1):
                    ne = even + (d%2==0)
                    no = odd + (d%2==1)
                    res += dp(pos+1, ne, no, (mod*10+d)%k, tight and d==up)
                return res
            return dp(0,0,0,0,True)
        return f(high) - f(low-1)
1

// Rust implementation omitted for brevity (use digit DP as above)

1

// TypeScript implementation omitted for brevity (use digit DP as above)

Complexity

  • ⏰ Time complexity: O(D^2 * N * K) (D = number of digits, N = max digits, K = divisor)
  • 🧺 Space complexity: O(D^2 * N * K)