Count Symmetric Integers

Difficulty: Easy | Acceptance: 83.00% | Paid: No Topics: Math, Enumeration

You are given two positive integers low and high.

An integer x is symmetric if the sum of the first half of the digits equals the sum of the second half of the digits. The number of digits must be even.

Return the count of symmetric integers in the range [low, high].

• Examples
• Constraints
• Approach 1: String Conversion
• Approach 2: Mathematical Digit Extraction
• Approach 3: Precomputation

Examples

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, 99.

Input: low = 1200, high = 1230
Output: 4
Explanation: There are 4 symmetric integers between 1200 and 1230: 1203, 1212, 1221, 1230.

Constraints

1 <= low <= high <= 10^4

Approach 1: String Conversion

Intuition Convert each number to a string to easily access individual digits and check the length. If the length is even, split the string in half and compare the sums of the characters.

Steps

• Initialize a counter to 0.
• Iterate through each number from low to high (inclusive).
• Convert the number to a string.
• If the string length is odd, skip the number.
• Calculate the sum of the first half of the characters and the second half.
• If the sums are equal, increment the counter.
• Return the counter.

class Solution:
    def countSymmetricIntegers(self, low: int, high: int) -> int:
        count = 0
        for num in range(low, high + 1):
            s = str(num)
            n = len(s)
            if n % 2 != 0:
                continue
            half = n // 2
            sum1 = sum(int(c) for c in s[:half])
            sum2 = sum(int(c) for c in s[half:])
            if sum1 == sum2:
                count += 1
        return count

Complexity

• Time: O(N * D) where N is the size of the range and D is the number of digits (max 5).
• Space: O(D) to store the string representation.
• Notes: Simple to implement but involves string allocation overhead.

Approach 2: Mathematical Digit Extraction

Intuition Instead of converting to a string, use modulo and division operations to extract digits. This avoids string allocation and is generally more performant in lower-level languages.

Steps

• Initialize a counter to 0.
• Iterate through each number from low to high.
• Extract digits into a list or array by repeatedly taking num % 10 and dividing num by 10.
• If the number of digits is odd, skip.
• Sum the first half and the second half of the extracted digits.
• Compare sums and update the counter.

class Solution:
    def countSymmetricIntegers(self, low: int, high: int) -> int:
        count = 0
        for num in range(low, high + 1):
            digits = []
            temp = num
            while temp > 0:
                digits.append(temp % 10)
                temp //= 10
            digits.reverse()
            n = len(digits)
            if n % 2 != 0:
                continue
            half = n // 2
            sum1 = sum(digits[:half])
            sum2 = sum(digits[half:])
            if sum1 == sum2:
                count += 1
        return count

Complexity

• Time: O(N * D) where N is the range size and D is the number of digits.
• Space: O(D) to store the digits array.
• Notes: Avoids string overhead, suitable for environments where string manipulation is expensive.

Approach 3: Precomputation

Intuition Since the constraint high is limited to 10⁴, there are only a finite number of symmetric integers. We can precompute all symmetric integers up to 10⁴ once and store them in a set. Then, for any query, we simply iterate through the range and check membership in the set.

Steps

• Generate all numbers from 1 to 10⁴.
• Check if each number is symmetric (using logic from Approach 1 or 2).
• Store valid numbers in a HashSet (or Set).
• Iterate from low to high and count how many numbers are present in the set.

class Solution:
    def __init__(self):
        self.symmetric_set = set()
        for num in range(1, 10001):
            s = str(num)
            n = len(s)
            if n % 2 != 0:
                continue
            half = n // 2
            if sum(int(c) for c in s[:half]) == sum(int(c) for c in s[half:]):
                self.symmetric_set.add(num)

    def countSymmetricIntegers(self, low: int, high: int) -> int:
        count = 0
        for num in range(low, high + 1):
            if num in self.symmetric_set:
                count += 1
        return count

Complexity

• Time: O(1) for the query logic (iterating range is O(N), but the check is O(1)), O(10⁴) for precomputation.
• Space: O(10⁴) to store the set of valid numbers.
• Notes: Best for multiple queries, but overkill for a single query given the small constraints.