Number of Beautiful Integers in the Range

Number of Beautiful Integers in the Range

What is this problem about?

The Number of Beautiful Integers in the Range problem asks you to count integers in [low, high] where: (1) every digit appears an equal number of times (or all digits have the same frequency), and (2) the integer is divisible by k. This hard coding problem uses digit DP to count valid integers within a range while tracking multiple constraints simultaneously.

Why is this asked in interviews?

Infosys asks this hard problem to test digit DP with multiple state dimensions. The problem requires tracking: current position, current divisibility mod k, and the balance of odd vs even digits (as a proxy for equal-frequency check). The math and dynamic programming interview pattern is the core, with digit DP as the technique.

Algorithmic pattern used

Digit DP. Compute count(high) - count(low-1). For count(n), define dp[pos][mod][evenDigits - oddDigits][tight][started]. Process digits left to right. Track: current modulo k, the count difference between even and odd digits (to check equal frequency). At the end, count states where mod=0 and the balance=0 (equal count of even and odd digits).

Example explanation

Range [1, 100], k=2. Count "beautiful" numbers where digit frequencies are equal AND divisible by 2.

• Numbers like 12 (digit 1: count 1, digit 2: count 1 — equal frequency ✓). 12 divisible by 2 ✓. Valid.
• 10 (digit 1: count 1, digit 0: count 1 ✓, divisible by 2 ✓). Valid. Count all such numbers in the range using digit DP.

Common mistakes candidates make

• Not understanding the "equal frequency" condition — it means each digit that appears, appears the same number of times.
• Using the wrong state representation for frequency balance.
• Digit DP bounds: compute count(high) - count(low-1), not count(high) - count(low).
• Not memoizing the DP (exponential without memoization).

Interview preparation tip

Digit DP problems with multiple simultaneous constraints require carefully designed state spaces. Before coding, explicitly list all constraints and define the DP state that captures them: position, tightness, leading zeros, and constraint-specific state (here: mod k and digit frequency balance). Practice classic digit DP problems (count numbers with digit sum S, count numbers with no two adjacent same digits) before tackling multi-constraint variants. Multi-constraint digit DP appears in hard-level Google and Infosys interviews.