Watch 10 video solutions for Count Symmetric Integers, a easy level problem involving Math, Enumeration. This walkthrough by codestorywithMIK has 6,340 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |