You are given two positive integers low and high.
An integer x consisting of 2 * n digits is symmetric if the sum of the first n digits of x is equal to the sum of the last n digits of x. Numbers with an odd number of digits are never symmetric.
Return the number of symmetric integers in the range [low, high].
Example 1:
Input: low = 1, high = 100 Output: 9 Explanation: There are 9 symmetric integers between 1 and 100: 11, 22, 33, 44, 55, 66, 77, 88, and 99.
Example 2:
Input: low = 1200, high = 1230 Output: 4 Explanation: There are 4 symmetric integers between 1200 and 1230: 1203, 1212, 1221, and 1230.
Constraints:
1 <= low <= high <= 104Problem Overview: You are given two integers low and high. Count how many numbers in this range are symmetric. A number is symmetric if it has an even number of digits and the sum of the first half of digits equals the sum of the second half.
Approach 1: Brute Force Enumeration (Time: O(n * d), Space: O(1))
Iterate through every integer from low to high. Convert the number to a string (or extract digits using division). If the digit count is odd, skip it immediately. Otherwise split the digits into two halves, compute the sum of each half, and compare them. If the sums match, increment the answer.
This approach relies purely on enumeration, making it straightforward to implement. The cost comes from processing digits for every number in the range. With d representing the number of digits, the complexity becomes O(n * d). Given the constraint that numbers are at most 5 digits, this runs comfortably fast.
Approach 2: Digit Analysis (Time: O(n), Space: O(1))
Instead of handling digits generically, analyze the possible digit lengths directly. Within the problem constraints, only 2-digit and 4-digit numbers can be symmetric. For 2-digit numbers, the condition reduces to a == b. For 4-digit numbers abcd, the rule becomes a + b == c + d.
Iterate through the range and apply these checks using arithmetic operations such as division and modulo to extract digits. This avoids string conversion and minimizes per-number work. Each number is checked in constant time, giving overall O(n) time and O(1) space.
This solution uses simple number manipulation techniques from math and systematic range scanning from enumeration. The key insight is recognizing that symmetric numbers only exist for even digit counts and that the comparison reduces to two small digit sums.
Recommended for interviews: Start with the brute force enumeration to demonstrate correctness and clarity. Then optimize with digit analysis by avoiding string conversions and handling only valid digit lengths. Interviewers typically expect the constant-time digit extraction approach since it shows comfort with numeric manipulation and edge-case reasoning.
This approach involves checking each integer in the range [low, high] to determine if it is symmetric. For each number, split its digits into two halves and check if their sums are equal.
For a number with 2n digits, calculate if the sum of the first n digits equals the sum of the last n digits. If equal, count it as a symmetric integer.
This C solution first converts the number to a string to analyze its digits. By iterating over half of the string and computing sums for both halves, it determines if a number is symmetric. The main function calls this helper function for every number in the range to count symmetric numbers.
Time Complexity: O(N * D), where N is the number of integers in the range and D is the number of digits in the number, due to conversion and summation.
Space Complexity: O(D), due to storage of the string representing the number.
This approach avoids checking each integer but analyzes digits for patterns. It constructs symmetric numbers by iterating over possible sums for halves within digit constraints. This quicker method leverages properties of digit sums and avoids visiting each candidate.
This solution in C iterates through potential digits, treating any pair of mirrored digits in a number. It calculates potential numbers by reconstructing them using two digits at even positions and mirrors them. It keeps track of valid symmetric numbers within the range.
Time Complexity: O(D^2), due to the nesting of two loops across potential digit values.
Space Complexity: O(1), no additional storage proportional to input size is used.
We enumerate each integer x in the range [low, high], and check whether it is a palindromic number. If it is, then the answer ans is increased by 1.
The time complexity is O(n times log m), and the space complexity is O(log m). Here, n is the number of integers in the range [low, high], and m is the maximum integer given in the problem.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(N * D), where N is the number of integers in the range and D is the number of digits in the number, due to conversion and summation. Space Complexity: O(D), due to storage of the string representing the number. |
| Digit Analysis Approach | Time Complexity: O(D^2), due to the nesting of two loops across potential digit values. Space Complexity: O(1), no additional storage proportional to input size is used. |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n * d) | O(1) | Best for clarity and quick implementation when constraints are small |
| Digit Analysis | O(n) | O(1) | Preferred in interviews; avoids string conversion and uses direct digit math |
Count Symmetric Integers | 2 Detailed Approaches | Leetcode 2843 | codestorywithMIK • codestorywithMIK • 6,340 views views
Watch 9 more video solutions →Practice Count Symmetric Integers with our built-in code editor and test cases.
Practice on FleetCode