LeetCode 2843 - Count Symmetric Integers

The problem asks us to count symmetric integers within a given range [low, high]. A symmetric integer is defined as an integer with an even number of digits, where the sum of the first half of the digits is equal to the sum of the second half.

leetcodeeasymathenumeration

LeetCode Problem 2843

Difficulty: 🟢 Easy
Topics: Math, Enumeration

Solution

Problem Understanding

The problem asks us to count symmetric integers within a given range [low, high]. A symmetric integer is defined as an integer with an even number of digits, where the sum of the first half of the digits is equal to the sum of the second half. For example, 1221 is symmetric because the sum of the first two digits 1 + 2 = 3 equals the sum of the last two digits 2 + 1 = 3. Numbers with an odd number of digits are automatically excluded because they cannot be split evenly into two halves.

The input consists of two integers low and high, which define the inclusive range to search. The expected output is a single integer, the count of symmetric numbers within that range.

The constraints indicate that the values of low and high are small (1 <= low <= high <= 10^4). This means we can afford a linear scan over the range without worrying about performance. The main edge cases are small ranges, ranges that include single-digit or three-digit numbers (which cannot be symmetric), and ranges that include the boundary numbers like 1 and 10000.

Approaches

The brute-force approach is straightforward: iterate over all integers in the range [low, high], skip numbers with an odd number of digits, and for numbers with an even number of digits, compute the sum of the first half and the second half of the digits. If the sums are equal, increment a counter. This approach works because it directly implements the problem definition, but for larger constraints it could be slow. For the current limits, it is feasible.

A key observation is that we only need to handle numbers with 2, 4, or possibly more digits up to 5 digits (since high <= 10^4). We can generate symmetric numbers systematically by splitting the number into halves and checking sums instead of iterating blindly. This allows us to avoid repeated conversions and summations, but for this problem, a simple iteration is sufficient due to the small range.

Approach Time Complexity Space Complexity Notes
Brute Force O(N * d) O(1) Iterates through range [low, high] and checks each number digit-wise for symmetry
Optimal O(N * d) O(1) Same as brute force due to small constraints, but could precompute sums for larger ranges

Here, N = high - low + 1 and d is the number of digits in each number.

Algorithm Walkthrough

  1. Initialize a counter count to zero. This will track the number of symmetric integers found.
  2. Loop over each integer x from low to high inclusive.
  3. Convert the integer x into a string to easily access digits. Check the number of digits len(x_str).
  4. If the number of digits is odd, skip this number since it cannot be symmetric.
  5. Split the number into two halves: first_half and second_half. Convert each digit in the halves to an integer.
  6. Compute the sum of the digits in first_half and second_half.
  7. If the sums are equal, increment count.
  8. After looping through all numbers, return count.

Why it works: The algorithm directly implements the definition of a symmetric integer. By checking every number in the range and ensuring the sums of the halves match, we are guaranteed to count all and only symmetric integers.

Python Solution

class Solution:
    def countSymmetricIntegers(self, low: int, high: int) -> int:
        count = 0
        for x in range(low, high + 1):
            x_str = str(x)
            n = len(x_str)
            if n % 2 != 0:
                continue
            mid = n // 2
            first_half_sum = sum(int(d) for d in x_str[:mid])
            second_half_sum = sum(int(d) for d in x_str[mid:])
            if first_half_sum == second_half_sum:
                count += 1
        return count

The implementation follows the algorithm directly. Each number is converted to a string to make it easy to split into halves. The sums of the two halves are compared, and the count is incremented only when the sums match.

Go Solution

func countSymmetricIntegers(low int, high int) int {
    count := 0
    for x := low; x <= high; x++ {
        xStr := fmt.Sprintf("%d", x)
        n := len(xStr)
        if n % 2 != 0 {
            continue
        }
        mid := n / 2
        firstSum, secondSum := 0, 0
        for i := 0; i < mid; i++ {
            firstSum += int(xStr[i] - '0')
            secondSum += int(xStr[i+mid] - '0')
        }
        if firstSum == secondSum {
            count++
        }
    }
    return count
}

The Go implementation differs slightly in handling strings and character-to-integer conversion. The rest of the logic mirrors the Python version.

Worked Examples

Example 1: low = 1, high = 100

Looping through numbers, the first symmetric numbers are 11, 22, 33, 44, 55, 66, 77, 88, 99. Count = 9.

x n first_half_sum second_half_sum symmetric? count
1-10 1 - - no 0
11 2 1 1 yes 1
22 2 2 2 yes 2
... ... ... ... ... ...
99 2 9 9 yes 9

Example 2: low = 1200, high = 1230

Symmetric numbers are 1203 (1+2=0+3), 1212 (1+2=1+2), 1221 (1+2=2+1), 1230 (1+2=3+0). Count = 4.

Complexity Analysis

Measure Complexity Explanation
Time O(N * d) Iterate through N numbers and sum digits (d digits per number)
Space O(1) Only counters and temporary sums, no extra data structures

The algorithm is efficient given the constraints. For ranges up to 10^4, the number of operations is acceptable.

Test Cases

# Basic examples
assert Solution().countSymmetricIntegers(1, 100) == 9  # example 1
assert Solution().countSymmetricIntegers(1200, 1230) == 4  # example 2

# Edge cases
assert Solution().countSymmetricIntegers(1, 1) == 0  # single-digit number
assert Solution().countSymmetricIntegers(11, 11) == 1  # smallest two-digit symmetric
assert Solution().countSymmetricIntegers(10000, 10000) == 0  # five-digit number, cannot be symmetric
assert Solution().countSymmetricIntegers(10, 99) == 9  # two-digit range only
assert Solution().countSymmetricIntegers(100, 999) == 0  # three-digit numbers, none symmetric
Test Why
1-100 Validates small range with single- and double-digit numbers
1200-1230 Checks four-digit numbers with partial range
1-1 Tests single-digit edge case
11-11 Smallest symmetric number
10000 Excludes five-digit numbers
10-99 Confirms counting all two-digit symmetric numbers
100-999 Ensures odd-digit numbers are skipped

Edge Cases

Single-digit ranges: Any number with 1 digit is never symmetric, so the algorithm correctly skips them using the n % 2 != 0 check.

Odd-digit numbers: Numbers with 3 or 5 digits should not be counted. Our string-length check guarantees these numbers are ignored.

Maximum boundary: The largest input 10000 has 5 digits, so it cannot be symmetric. The algorithm safely skips it, avoiding errors from indexing or sum calculations.

This implementation handles all these cases correctly without special casing.