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:
low = 1
, and high = 100
, return 9
. The symmetric integers are 11, 22, 33, 44, 55, 66, 77, 88, and 99.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
.
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
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