#2843

Easy

LeetCode Problem Workspace

Count Symmetric Integers

Count Symmetric Integers finds numbers where the sum of the first half of digits equals the sum of the second half within a range.

math enumeration

Problem Statement

You are given two integers, low and high. Your task is to count how many symmetric integers exist in the range [low, high]. A symmetric integer is a number with an even number of digits where the sum of the first half of digits equals the sum of the second half.

Numbers with an odd number of digits can never be symmetric. The task is to find all such numbers within the range, ensuring you account for all valid cases where symmetry holds.

Examples

Example 1

Input: low = 1, high = 100

Output: 9

There are 9 symmetric integers between 1 and 100: 11, 22, 33, 44, 55, 66, 77, 88, and 99.

Example 2

Input: low = 1200, high = 1230

Output: 4

There are 4 symmetric integers between 1200 and 1230: 1203, 1212, 1221, and 1230.

Constraints

1 <= low <= high <= 104

Solution Approach

Iterate through the Range

Loop through all numbers in the range from low to high. For each number, check if it has an even number of digits and compute the sum of the first half and second half of its digits.

Check Symmetry of Each Number

For every even-digit number, split it into two halves and compare the sums of digits from each half. If the sums are equal, it is considered symmetric.

Efficient Counting

Given the constraints, a simple iteration and summation of digits for each number in the range is sufficient, with the time complexity being linear in the size of the range.

Complexity Analysis

Metric	Value
Time	O(high - low)
Space	O(1)

The time complexity is O(high - low), as we iterate over each number in the given range. The space complexity is O(1) because we only need a constant amount of space for the sum calculations.

What Interviewers Usually Probe

The candidate understands how to handle number manipulation and splitting digits.
The candidate correctly identifies the need for a linear approach in iterating through the range.
The candidate demonstrates a strong understanding of problem constraints and the symmetry condition.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check if a number has an even number of digits, leading to incorrect results for numbers with odd digits.
Incorrectly splitting the digits of a number, causing errors in calculating the sums.
Not iterating through all numbers in the range [low, high], missing some valid cases.

Follow-up variants

Modify the range to include negative integers and consider their behavior.
Extend the problem to support large numbers with more than 4 digits.
Consider using a different approach that avoids iterating through every number in the range.

FAQ

What is the time complexity of solving Count Symmetric Integers?

The time complexity is O(high - low), as we iterate over each number in the range and perform constant-time operations to check for symmetry.

Can numbers with an odd number of digits be symmetric?

No, numbers with an odd number of digits cannot be symmetric, as there is no way to split them into two equal halves.

How should I split a number to check symmetry?

For each number with an even number of digits, split it into two halves, then check if the sum of the digits in the first half equals the sum in the second half.

How can GhostInterview assist with the Count Symmetric Integers problem?

GhostInterview guides you through iterating over ranges, checking symmetry conditions, and avoiding common pitfalls such as improper digit splitting.

What are some common pitfalls when solving the Count Symmetric Integers problem?

Common pitfalls include forgetting to check for even-digit numbers, incorrect digit splitting, and missing numbers in the range due to faulty iteration.

terminal

Solution

Solution 1: Enumeration

We enumerate each integer $x$ in the range $[low, high]$, and check whether it is a palindromic number. If it is, then the answer $ans$ is increased by $1$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def countSymmetricIntegers(self, low: int, high: int) -> int:
        def f(x: int) -> bool:
            s = str(x)
            if len(s) & 1:
                return False
            n = len(s) // 2
            return sum(map(int, s[:n])) == sum(map(int, s[n:]))

        return sum(f(x) for x in range(low, high + 1))

Continue Practicing

#2844 minimum operations to make a special number #2761 prime pairs with target sum #2928 distribute candies among children i