Taro Logo

Count Symmetric Integers

Easy
Apple logo
Apple
7 views
Topics:
ArraysStrings

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].

For example:

  1. If low = 1, and high = 100, return 9. The symmetric integers are 11, 22, 33, 44, 55, 66, 77, 88, and 99.
  2. If low = 1200, and high = 1230, return 4. The symmetric integers are 1203, 1212, 1221, and 1230.

Write a function to efficiently count the number of symmetric integers within a given range. Consider the constraints: 1 <= low <= high <= 10^4.

Solution


Brute Force Solution

A naive approach would be to iterate through all numbers in the given range [low, high] and, for each number, check if it's symmetric. To check if a number is symmetric, we convert it to a string, and if the length of the string is even, we split it into two halves and compare the sum of digits in each half.

def is_symmetric(n):
    s = str(n)
    if len(s) % 2 != 0:
        return False
    mid = len(s) // 2
    left_sum = sum(int(digit) for digit in s[:mid])
    right_sum = sum(int(digit) for digit in s[mid:])
    return left_sum == right_sum


def count_symmetric_brute_force(low, high):
    count = 0
    for i in range(low, high + 1):
        if is_symmetric(i):
            count += 1
    return count

Complexity Analysis

  • Time Complexity: O((high - low + 1) * log10(high)), where log10(high) represents the number of digits in the number, as we iterate through each number in the range and then iterate through the digits of that number.
  • Space Complexity: O(1), excluding the string representation.

Optimal Solution

For the constraints given (1 <= low <= high <= 104), we can precompute symmetric numbers up to 10000 and then count how many fall within the range [low, high]. We generate all symmetric numbers with 2 digits and 4 digits (since numbers with an odd number of digits are not symmetric). Then, we simply iterate through the range and see how many numbers are present from our generated list.

def generate_symmetric_numbers(max_val):
    symmetric_numbers = []

    # Generate 2-digit symmetric numbers
    for i in range(1, 10):
        num = i * 10 + i
        symmetric_numbers.append(num)

    # Generate 4-digit symmetric numbers
    for i in range(1, 10):
        for j in range(0, 10):
            num = i * 1000 + j * 100 + j * 10 + i
            if num <= max_val:
                symmetric_numbers.append(num)
            else:
                break #optimization
    symmetric_numbers.sort()
    return symmetric_numbers


def count_symmetric(low, high):
    symmetric_numbers = generate_symmetric_numbers(high)
    count = 0
    for num in symmetric_numbers:
        if low <= num <= high:
            count += 1
    return count

Complexity Analysis

  • Time Complexity: O(1). Generating symmetric numbers is constant time because the range of numbers is fixed. Finding the symmetric numbers in the range low and high is also O(1) as the precomputed array is relatively small.
  • Space Complexity: O(1). The space used to store symmetric numbers is constant because it depends on the maximum number of digits and is capped.

Edge Cases

  • low and high are the same: Check if the single number is symmetric.
  • low and high are close to the extremes: The code handles this naturally due to the problem's constraints.
  • Empty range (low > high): Should return 0, which is handled correctly by the code.