Problem Description

You need to find how many "symmetric" integers exist within a given range [low, high].

A symmetric integer is defined as follows:

• The integer must have an even number of digits (2 * n digits total)
• When you split the number in half, the sum of the first n digits must equal the sum of the last n digits
• Numbers with an odd number of digits can never be symmetric

For example:

• 1221 is symmetric because it has 4 digits (even), and the sum of first 2 digits (1+2=3) equals the sum of last 2 digits (2+1=3)
• 123 cannot be symmetric because it has 3 digits (odd)
• 1234 is not symmetric because it has 4 digits, but the sum of first 2 digits (1+2=3) doesn't equal the sum of last 2 digits (3+4=7)

The solution works by checking each number in the range [low, high]:

1. Convert the number to a string to easily access individual digits
2. Check if the length is odd - if yes, return False immediately
3. If the length is even, split the string in half
4. Calculate the sum of digits in the first half and the sum of digits in the second half
5. Return True if these sums are equal, False otherwise

The function f(x) performs this check for a single number x, and the main solution counts how many numbers in the range satisfy this condition.

Intuition

The most straightforward way to solve this problem is to check every number in the given range individually. Since we need to count how many numbers satisfy a specific condition, and there's no mathematical pattern that would allow us to calculate the count directly, we need to examine each number.

The key insight is that we can treat the number as a string to easily access and manipulate individual digits. This avoids complex mathematical operations like repeatedly dividing by 10 and using modulo to extract digits.

For each number, we need to:

1. First filter out numbers with odd digit counts since they can never be symmetric by definition
2. Split the remaining even-digit numbers exactly in half
3. Compare the digit sums of both halves

The beauty of this approach is its simplicity - we're directly implementing what the problem asks for without trying to optimize prematurely. Since we're dealing with positive integers and a bounded range, the brute force approach is perfectly acceptable.

Using Python's string slicing makes the implementation clean: s[:n] gives us the first half and s[n:] gives us the second half when n is the midpoint. The sum(map(int, s[:n])) construct elegantly converts each character to an integer and sums them in one expression.

The time complexity is O(m * d) where m is the number of integers in the range and d is the average number of digits, which is reasonable for the constraints typically found in such problems.

Learn more about Math patterns.

Solution Approach

The solution uses an enumeration approach to check every integer in the range [low, high].

The implementation consists of two parts:

1. Helper Function f(x): This function determines whether a given integer x is symmetric.

   • Convert the integer to a string: s = str(x)
   • Check if the length is odd using bitwise AND: if len(s) & 1. This is equivalent to len(s) % 2 == 1 but slightly more efficient
   • If odd, immediately return False since odd-digit numbers cannot be symmetric
   • Calculate the midpoint: n = len(s) // 2
   • Extract and sum the first half: sum(map(int, s[:n]))
   • Extract and sum the second half: sum(map(int, s[n:]))
   • Compare the two sums and return the result

2. Main Solution: Count all symmetric integers in the range.

   • Use a generator expression with sum() to count: sum(f(x) for x in range(low, high + 1))
   • This iterates through each number from low to high (inclusive)
   • For each number, f(x) returns True (1) or False (0)
   • The sum() function adds up all the True values, giving us the final count

The algorithm leverages Python's string slicing capabilities:

• s[:n] gets characters from index 0 to n-1 (first half)
• s[n:] gets characters from index n to the end (second half)

The map(int, s[:n]) pattern converts each character digit to its integer value, allowing us to sum them directly.

This brute-force approach examines each number exactly once, making it O(m) where m is the size of the range [low, high], with each check taking O(d) time where d is the number of digits in the number.

Example Walkthrough

Let's walk through finding all symmetric integers in the range [low=1200, high=1230].

Step 1: Check each number from 1200 to 1230

For x = 1200:

• Convert to string: s = "1200"
• Length is 4 (even), so continue
• Calculate midpoint: n = 4 // 2 = 2
• First half: s[:2] = "12", sum = 1 + 2 = 3
• Second half: s[2:] = "00", sum = 0 + 0 = 0
• Since 3 ≠ 0, return False

For x = 1201:

• Convert to string: s = "1201"
• Length is 4 (even), so continue
• First half: "12", sum = 1 + 2 = 3
• Second half: "01", sum = 0 + 1 = 1
• Since 3 ≠ 1, return False

For x = 1210:

• Convert to string: s = "1210"
• Length is 4 (even), so continue
• First half: "12", sum = 1 + 2 = 3
• Second half: "10", sum = 1 + 0 = 1
• Since 3 ≠ 1, return False

For x = 1212:

• Convert to string: s = "1212"
• Length is 4 (even), so continue
• First half: "12", sum = 1 + 2 = 3
• Second half: "12", sum = 1 + 2 = 3
• Since 3 = 3, return True ✓

For x = 1221:

• Convert to string: s = "1221"
• Length is 4 (even), so continue
• First half: "12", sum = 1 + 2 = 3
• Second half: "21", sum = 2 + 1 = 3
• Since 3 = 3, return True ✓

For x = 1230:

• Convert to string: s = "1230"
• Length is 4 (even), so continue
• First half: "12", sum = 1 + 2 = 3
• Second half: "30", sum = 3 + 0 = 3
• Since 3 = 3, return True ✓

Step 2: Count the symmetric numbers

The symmetric numbers found are: 1212, 1221, and 1230.

Final Answer: 3

The algorithm correctly identifies that 3 numbers in the range [1200, 1230] are symmetric by checking each number's digit sum equality after splitting them in half.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log m)

The algorithm iterates through all integers from low to high, giving us n = high - low + 1 iterations. For each integer x in this range, the function f(x) is called, which:

• Converts the integer to a string: O(log m) where m is the value of the integer (since the number of digits is proportional to log m)
• Checks the length and performs string slicing: O(log m)
• Computes the sum of digits for both halves: O(log m) operations

Therefore, the overall time complexity is O(n × log m) where n is the number of integers in the range [low, high] and m is the maximum value in the range.

Space Complexity: O(log m)

The space complexity is determined by:

• String conversion of integer x: requires O(log m) space to store the string representation
• String slicing creates two new strings s[:n] and s[n:]: each requires O(log m) space
• The map function and intermediate computations use O(log m) space

Since these operations are not nested and the space is reused for each integer in the iteration, the overall space complexity is O(log m) where m is the maximum integer value being processed.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Single-Digit Numbers

A common mistake is forgetting that single-digit numbers (1-9) have an odd number of digits and therefore cannot be symmetric by definition. Some might incorrectly consider them symmetric since there's "nothing to compare."

Wrong approach:

def is_symmetric(number):
    num_str = str(number)
    if len(num_str) == 1:
        return True  # WRONG: Single digits are not symmetric
    # ... rest of the code

Correct approach: The original solution correctly handles this by checking if the length is odd and returning False immediately.

2. Off-by-One Error in Range Iteration

The problem specifies an inclusive range [low, high], but Python's range() function is exclusive of the end value. Forgetting to add 1 to high will miss the last value.

Wrong approach:

symmetric_count = sum(is_symmetric(x) for x in range(low, high))  # Misses 'high'

Correct approach:

symmetric_count = sum(is_symmetric(x) for x in range(low, high + 1))  # Includes 'high'

3. Integer Division vs Float Division

When calculating the midpoint, using float division (/) instead of integer division (//) would cause string slicing errors.

Wrong approach:

mid = len(num_str) / 2  # Returns float, causes TypeError in slicing
first_half = num_str[:mid]  # ERROR: slice indices must be integers

Correct approach:

mid = len(num_str) // 2  # Returns integer for proper slicing

4. Misunderstanding the Symmetry Definition

Some might confuse this problem with palindromes or think symmetry means the digits themselves should be equal rather than their sums.

Wrong interpretation:

def is_symmetric(number):
    num_str = str(number)
    if len(num_str) & 1:
        return False
    mid = len(num_str) // 2
    return num_str[:mid] == num_str[mid:]  # WRONG: Comparing strings, not sums

Correct interpretation: The solution should compare the sum of digits in each half, not the digits themselves or their arrangement.

5. Performance Consideration for Large Ranges

While not incorrect, the brute-force approach can be inefficient for very large ranges. For competitive programming with tight time limits, consider optimizing by:

• Using digit DP (dynamic programming) approaches for counting symmetric numbers
• Pre-calculating symmetric numbers for specific digit lengths
• Using mathematical patterns to skip impossible ranges

Example optimization for specific cases:

def count_symmetric_optimized(low, high):
    # Skip ranges that contain only odd-digit numbers
    if high < 10:  # All single-digit
        return 0
    if low >= 10 and high < 100:  # All two-digit numbers
        # Can calculate directly: numbers where both digits are equal
        return len([x for x in range(low, high + 1) if x // 10 == x % 10])
    # ... continue with regular approach for mixed ranges