Hard

Number of Beautiful Integers in the Range

LAB

Return how many integers in [low,high] are divisible by k and have the same count of odd and even digits.

EXAMPLES

Example 1

Input
{
  "low": 10,
  "high": 20,
  "k": 3
}

Output
2

FUNCTION SHAPE

low: inthigh: intk: int→int

SOLUTION NOTE

Track: position, tight bound, started, odd-even diff, remainder mod k. Count in [0, high] - [0, low-1].

Reveal reference solution +

pythonREFERENCE

def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:
    def count(num):
        s = str(num)
        n = len(s)

        @cache
        def dp(i, tight, started, diff, mod):
            if i == n:
                return 1 if started and diff == 0 and mod == 0 else 0

            limit = int(s[i]) if tight else 9
            res = 0

            for d in range(0, limit + 1):
                new_tight = tight and (d == limit)
                new_started = started or (d > 0)

                if not new_started:
                    res += dp(i + 1, new_tight, False, 0, 0)
                else:
                    new_diff = diff + (1 if d % 2 == 1 else -1)
                    new_mod = (mod * 10 + d) % k
                    res += dp(i + 1, new_tight, True, new_diff, new_mod)

            return res

        return dp(0, True, False, 0, 0)

    return count(high) - count(low - 1)

TimeO(n × k × n)

SpaceO(n × k × n)

Open on LeetCode ↗