Skip to main content
Talentd

Number of Beautiful Integers in the Range - Solution & Explanation

HardMathDynamic Programming26 min readAsked at: Infosys
Practice this problem

Problem Statement

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

 

Example 1:

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:

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:

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 <= 109
  • 0 < k <= 20

Approach Overview

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.

Approach 1: Brute Force Approach

This approach involves iterating through each number within the range of low to high and checking if each number is beautiful—i.e., it has an equal number of even and odd digits and is divisible by k.

For each number, we convert it to a string to count the digits that are even or odd, and subsequently check divisibility by k.

This C code defines a helper function isBeautiful to check if a number has equal numbers of even and odd digits and is divisible by k. It iterates through each number in the given range, checks its conditions and adjusts a counter accordingly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * d), where n is the count of numbers in the range and d is the number of digits per number.
Space Complexity: O(1), since there are no data structures that grow with input size.

Try this approach in the editor →

Approach 2: Digit Dynamic Programming (DP)

This approach leverages digit dynamic programming. By analyzing number structure through dynamic programming, you avoid separately analyzing each number iteratively. Use a DP table to maintain the count of numbers up to a digit length that meets the criteria (equal evens and odds).

This can be optimized by precomputing balances and leveraging symmetry in evens and odds.

Providing a DP solution for beautiful number calculation in C is impractical due to lack of built-in libraries and need for excessive code verbosity without external dependencies.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Typical DP solutions would involve optimized runtimes but require extremely elaborate code under C, hence not practical for inline presentations.

Try this approach in the editor →

Approach 3: Digit DP

We notice that the problem is asking for the number of beautiful integers in the interval [low, high]. For such an interval [l,..r] problem, we can usually consider transforming it into finding the answers for [1, r] and [1, l-1], and then subtracting the latter from the former. Moreover, the problem only involves the relationship between different digits, not the specific values, so we can consider using Digit DP to solve it.

We design a function dfs(pos, mod, diff, lead, limit), which represents the number of schemes when we are currently processing the pos-th digit, the result of the current number modulo k is mod, the difference between the odd and even digits of the current number is diff, whether the current number has leading zeros is lead, and whether the current number has reached the upper limit is limit.

The execution logic of the function dfs(pos, mod, diff, lead, limit) is as follows:

If pos exceeds the length of num, it means that we have processed all the digits. If mod=0 and diff=0 at this time, it means that the current number meets the requirements of the problem, so we return 1, otherwise we return 0.

Otherwise, we calculate the upper limit up of the current digit, and then enumerate the digit i in the range [0,..up]:

  • If i=0 and lead is true, it means that the current number only contains leading zeros. We recursively calculate the value of dfs(pos + 1, mod, diff, 1, limit\ and\ i=up) and add it to the answer.
  • Otherwise, we update the value of diff according to the parity of i, and then recursively calculate the value of dfs(pos + 1, (mod times 10 + i) bmod k, diff, 0, limit\ and\ i=up) and add it to the answer.

Finally, we return the answer.

In the main function, we calculate the answers a and b for [1, high] and [1, low-1] respectively. The final answer is a-b.

The time complexity is O((log M)^2 times k times |\Sigma|), and the space complexity is O((log M)^2 times k), where M represents the size of the number high, and |\Sigma| represents the digit set.

Similar problems:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n * d), where n is the count of numbers in the range and d is the number of digits per number.
Space Complexity: O(1), since there are no data structures that grow with input size.

Digit Dynamic Programming (DP)

Typical DP solutions would involve optimized runtimes but require extremely elaborate code under C, hence not practical for inline presentations.

Digit DP—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(N * D)O(1)Small ranges where high - low is limited and performance is not critical
Digit Dynamic Programming (Digit DP)O(D^2 * K)O(D * K * D)Large numeric ranges with digit constraints and divisibility checks

Video Solution

2827. Number of Beautiful Integers in the Range | Digit DP| Leetcode Biweekly 111 • codingMohan • 2,010 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Number of Beautiful Integers in the Range easy or hard?
Number of Beautiful Integers in the Range is classified as a Hard problem because it combines multiple constraints: digit counting, divisibility, and range limits. Solving it efficiently requires understanding the Digit DP pattern and managing several DP states simultaneously.
Number of Beautiful Integers in the Range Python/Java solution
Python and Java solutions typically implement Digit DP with recursion and memoization. The function tracks the current index, digit balance, remainder modulo k, and tight flag. Memoization ensures each state is computed once, giving efficient performance even for large ranges.
How to solve Number of Beautiful Integers in the Range in O(d^2 * k)?
Use Digit Dynamic Programming. Process numbers digit by digit while maintaining DP state variables: position, remainder modulo k, even-odd digit balance, and a tight constraint flag. Count valid numbers up to high and subtract the count up to low - 1 to get the final result.
What is the best approach for Number of Beautiful Integers in the Range?
Digit Dynamic Programming (Digit DP) is the most efficient approach. Instead of iterating through every number in the range, it constructs valid numbers digit by digit while tracking constraints such as remainder modulo k and the difference between even and odd digit counts. This reduces the complexity to roughly O(d^2 * k), where d is the number of digits.
Is Number of Beautiful Integers in the Range asked at Google/Amazon/Meta?
Problems involving Digit DP and digit constraints frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the underlying pattern of counting numbers with digit properties and modular constraints is commonly tested.
What data structure is used in Number of Beautiful Integers in the Range?
The key technique is dynamic programming with memoization. A DP cache (often implemented with arrays or hash maps) stores states defined by digit index, modulo remainder, even-odd digit difference, and tight constraint to avoid recomputation.
What is the time complexity of Number of Beautiful Integers in the Range?
The optimal Digit DP solution runs in about O(d^2 * k) time, where d is the number of digits in the upper bound and k is the divisor. The brute force solution takes O(N * d), where N is the size of the range and d is the number of digits per number.

Ready to solve this problem?

Practice Number of Beautiful Integers in the Range with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Numbers with Non-Decreasing Digits