Number of Beautiful Integers in the Range - Video Solutions

Problem Overview: Given two integers low and high and an integer k, count how many numbers in the range satisfy two conditions: the number of even digits equals the number of odd digits, and the number is divisible by k. The challenge is that the range can be large, so checking every number directly is inefficient.

Approach 1: Brute Force Enumeration (Time: O(N * D), Space: O(1))

Iterate through every integer from low to high. For each number, extract digits and count how many are even and how many are odd. If the counts match, compute num % k to check divisibility. Digit processing takes O(D) where D is the number of digits, so the full scan costs O(N * D) where N = high - low + 1. This approach is easy to implement but becomes impractical when the range spans millions or billions of numbers.

Approach 2: Digit Dynamic Programming (Digit DP) (Time: O(D^2 * K), Space: O(D * K * D))

Instead of checking every number, build valid numbers digit by digit using dynamic programming. Convert the upper bound into a digit array and recursively construct numbers while tracking state: current digit index, difference between even and odd counts, current remainder modulo k, and whether the prefix is still constrained by the limit (tight flag). This technique is known as Digit DP and is common in counting problems involving digit constraints.

At each position, try placing digits 0–9. Update the even/odd balance and compute the new remainder using (prev_remainder * 10 + digit) % k. Memoize states that are no longer tight so repeated subproblems are computed once. Finally compute count(high) - count(low - 1) to get the result for the range. The number of states is bounded by digit length, remainder modulo k, and the even/odd balance, giving roughly O(D^2 * K) complexity.

This approach relies on ideas from math (modular arithmetic) and dynamic programming, especially the digit-state technique used in many range counting problems.

Recommended for interviews: Start by explaining the brute force method to show you understand the constraints and validation logic. Then move to Digit DP, which avoids scanning the entire range and counts valid numbers using state transitions. Interviewers expect the Digit DP optimization for large ranges because it reduces the search space dramatically while handling multiple digit constraints.