Number of Beautiful Integers in the Range

Hard
1639.

Number of Beautiful Integers in the Range

Number of Beautiful Integers in the Range is a hard coding problem on dynamic programming, math and Digit DP, asked in Amazon and Google interviews.

Call a positive integer beautiful for a given k when both of these hold:

  • its decimal representation has exactly as many even digits as odd digits, and
  • it is divisible by k.

Given low, high and k, return how many beautiful integers lie in the inclusive range [low, high].

Example 1

Input
low = 10, high = 20, k = 3
Output
2
Explanation
12 (one odd digit, one even) and 18 (likewise) are multiples of 3. 15 is a multiple of 3 but both its digits are odd.

Example 2

Input
low = 1, high = 10, k = 1
Output
1
Explanation
Only 10 has one odd and one even digit; every single-digit number is unbalanced.

Example 3

Input
low = 5, high = 5, k = 2
Output
0
Explanation
A one-digit number can never have equal counts.

Constraints

  • 0 < low <= high <= 10^9
  • 0 < k <= 20
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} low
 * @param {number} high
 * @param {number} k
 * @return {number}
 */
var numberOfBeautifulIntegers = function(low, high, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Beautiful Integers in the Range — Solution

Number of Beautiful Integers in the Range solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Number of Beautiful Integers in the Range is a hard coding problem on dynamic programming, math and Digit DP, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Dynamic Programming, Math, Digit DP
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Call a positive integer beautiful for a given k when both of these hold:

  • its decimal representation has exactly as many even digits as odd digits, and
  • it is divisible by k.

Given low, high and k, return how many beautiful integers lie in the inclusive range [low, high].

Example 1

Input: low = 10, high = 20, k = 3
Output: 2
Explanation: 12 (one odd digit, one even) and 18 (likewise) are multiples of 3. 15 is a multiple of 3 but both its digits are odd.

Example 2

Input: low = 1, high = 10, k = 1
Output: 1
Explanation: Only 10 has one odd and one even digit; every single-digit number is unbalanced.

Example 3

Input: low = 5, high = 5, k = 2
Output: 0
Explanation: A one-digit number can never have equal counts.

Constraints

  • 0 < low <= high <= 10^9
  • 0 < k <= 20

Hints for Number of Beautiful Integers in the Range

  1. Hint 1

    Count beautiful numbers in [1, n] with a function f(n); the answer is f(high) - f(low - 1).

  2. Hint 2

    Build numbers digit by digit from the most significant one (digit DP). What do you need to remember about the prefix so far to finish the decision?

  3. Hint 3

    Track four things: whether the prefix still equals n's prefix (tight), whether a non-zero digit has been placed yet (leading zeros are not digits), the remainder modulo k, and the difference between even and odd digit counts.

How to solve Number of Beautiful Integers in the Range

The range is too large to scan, but whether a number is beautiful depends only on two running quantities — its remainder modulo k and the balance of even versus odd digits — so a digit DP counts all numbers up to a bound at once.

Approach

  1. Write f(n) = beautiful numbers in [1, n]; return f(high) - f(low - 1).
  2. For f(n), walk the digits of n from the left. A state is (tight, started, rem, balance) with a count of prefixes in it; start from (tight, not started, 0, 0) with count 1.
  3. At each position try every digit g from 0 up to n's digit if tight, else 9. The new state stays tight only if it was tight and g equals the bound.
  4. If the number has not started and g = 0, it is still a leading zero: stay unstarted with remainder 0 and balance 0. Otherwise mark it started, set rem = (rem * 10 + g) mod k and add +1 to the balance for an even g, -1 for an odd one.
  5. After the last digit, add up the counts of started states with remainder 0 and balance 0.

Why it works

Two numbers whose prefixes agree on remainder and balance can be completed by exactly the same suffixes, so grouping prefixes by those values loses nothing. The tight flag keeps every counted number at most n, and the started flag keeps leading zeros out of the even-digit count.

Complexity

  • Time — O(D · k · D · 10) per bound, with D ≤ 10 digits
  • Space — O(k · D)

Pitfalls

  • Leading zeros are not even digits — without the started flag, 7 would be read as 07 and look balanced.
  • Use low - 1 for the lower bound, not low.
  • The balance can range from -10 to +10, so offset it before using it as an index.

Reference solution

Python

def numberOfBeautifulIntegers(low: int, high: int, k: int) -> int:
    # state index = ((tight * 2 + started) * k + rem) * 21 + balance + 10
    def count(n):
        if n <= 0:
            return 0
        size = 4 * k * 21
        cur = [0] * size
        cur[2 * k * 21 + 10] = 1
        for ch in str(n):
            top = ord(ch) - 48
            nxt = [0] * size
            for idx in range(size):
                c = cur[idx]
                if c == 0:
                    continue
                d = idx % 21
                r = (idx // 21) % k
                ts = idx // (21 * k)
                t, st = ts >> 1, ts & 1
                hi = top if t else 9
                for g in range(hi + 1):
                    nt = 1 if (t and g == hi) else 0
                    if not st and g == 0:
                        nxt[nt * 2 * k * 21 + 10] += c
                    else:
                        nd = d + 1 if g % 2 == 0 else d - 1
                        nxt[((nt * 2 + 1) * k + (r * 10 + g) % k) * 21 + nd] += c
            cur = nxt
        return cur[k * 21 + 10] + cur[3 * k * 21 + 10]

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

Java

static long beautifulUpTo(int n, int k) {
    // state index = ((tight * 2 + started) * k + rem) * 21 + balance + 10
    if (n <= 0) return 0;
    int size = 4 * k * 21;
    long[] cur = new long[size];
    cur[2 * k * 21 + 10] = 1;
    String digits = Integer.toString(n);
    for (int p = 0; p < digits.length(); p++) {
        int top = digits.charAt(p) - '0';
        long[] nxt = new long[size];
        for (int idx = 0; idx < size; idx++) {
            long c = cur[idx];
            if (c == 0) continue;
            int d = idx % 21, r = (idx / 21) % k, ts = idx / (21 * k);
            int t = ts >> 1, st = ts & 1;
            int hi = t == 1 ? top : 9;
            for (int g = 0; g <= hi; g++) {
                int nt = (t == 1 && g == hi) ? 1 : 0;
                if (st == 0 && g == 0) nxt[nt * 2 * k * 21 + 10] += c;
                else nxt[((nt * 2 + 1) * k + (r * 10 + g) % k) * 21 + d + (g % 2 == 0 ? 1 : -1)] += c;
            }
        }
        cur = nxt;
    }
    return cur[k * 21 + 10] + cur[3 * k * 21 + 10];
}

public static int numberOfBeautifulIntegers(int low, int high, int k) {
    return (int) (beautifulUpTo(high, k) - beautifulUpTo(low - 1, k));
}

C++

long long beautifulUpTo(int n, int k) {
    // state index = ((tight * 2 + started) * k + rem) * 21 + balance + 10
    if (n <= 0) return 0;
    int size = 4 * k * 21;
    vector<long long> cur(size, 0);
    cur[2 * k * 21 + 10] = 1;
    string digits = to_string(n);
    for (char ch : digits) {
        int top = ch - '0';
        vector<long long> nxt(size, 0);
        for (int idx = 0; idx < size; idx++) {
            long long c = cur[idx];
            if (c == 0) continue;
            int d = idx % 21, r = (idx / 21) % k, ts = idx / (21 * k);
            int t = ts >> 1, st = ts & 1;
            int hi = t ? top : 9;
            for (int g = 0; g <= hi; g++) {
                int nt = (t && g == hi) ? 1 : 0;
                if (!st && g == 0) nxt[nt * 2 * k * 21 + 10] += c;
                else nxt[((nt * 2 + 1) * k + (r * 10 + g) % k) * 21 + d + (g % 2 == 0 ? 1 : -1)] += c;
            }
        }
        cur = nxt;
    }
    return cur[k * 21 + 10] + cur[3 * k * 21 + 10];
}

int numberOfBeautifulIntegers(int low, int high, int k) {
    return (int) (beautifulUpTo(high, k) - beautifulUpTo(low - 1, k));
}

JavaScript

var numberOfBeautifulIntegers = function(low, high, k) {
    // state index = ((tight * 2 + started) * k + rem) * 21 + balance + 10
    var count = function(n) {
        if (n <= 0) return 0;
        var size = 4 * k * 21;
        var cur = new Array(size).fill(0);
        cur[2 * k * 21 + 10] = 1;
        var digits = String(n);
        for (var p = 0; p < digits.length; p++) {
            var top = digits.charCodeAt(p) - 48;
            var nxt = new Array(size).fill(0);
            for (var idx = 0; idx < size; idx++) {
                var c = cur[idx];
                if (c === 0) continue;
                var d = idx % 21, r = Math.floor(idx / 21) % k, ts = Math.floor(idx / (21 * k));
                var t = ts >> 1, st = ts & 1;
                var hi = t ? top : 9;
                for (var g = 0; g <= hi; g++) {
                    var nt = (t && g === hi) ? 1 : 0;
                    if (!st && g === 0) nxt[nt * 2 * k * 21 + 10] += c;
                    else nxt[((nt * 2 + 1) * k + (r * 10 + g) % k) * 21 + d + (g % 2 === 0 ? 1 : -1)] += c;
                }
            }
            cur = nxt;
        }
        return cur[k * 21 + 10] + cur[3 * k * 21 + 10];
    };
    return count(high) - count(low - 1);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming