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.

#2843

Easy

auto_awesome数学·结合·enumeration

LeetCode 题解工作台

统计对称整数的数目

给你两个正整数 low 和 high 。对于一个由 2 * n 位数字组成的整数 x ，如果其前 n 位数字之和与后 n 位数字之和相等，则认为这个数字是一个对称整数。返回在 [low, high] 范围内的对称整数的数目。示例 1：输入： low = 1, high = 100 输出：…

数学枚举

题目描述

给你两个正整数 low 和 high 。

对于一个由 2 * n 位数字组成的整数 x ，如果其前 n 位数字之和与后 n 位数字之和相等，则认为这个数字是一个对称整数。

返回在 [low, high] 范围内的 对称整数的数目 。

示例 1：

输入：low = 1, high = 100
输出：9
解释：在 1 到 100 范围内共有 9 个对称整数：11、22、33、44、55、66、77、88 和 99 。

示例 2：

输入：low = 1200, high = 1230
输出：4
解释：在 1200 到 1230 范围内共有 4 个对称整数：1203、1212、1221 和 1230 。

提示：

1 <= low <= high <= 10⁴

lightbulb

解题思路

方法一：枚举

我们枚举 $[low, high]$ 中的每个整数 $x$ ，判断其是否是对称整数。如果是，那么答案 $ans$ 增加 $1$ 。

时间复杂度 $O(n \times \log m)$ ，空间复杂度 $O(\log m)$ 。其中 $n$ 是 $[low, high]$ 中整数的个数，而 $m$ 是题目中给出的最大整数。

1

2

3

4

5

6

7

8

9

10

11

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))

speed

复杂度分析

指标	值
时间	O(high - low)
空间	O(1)

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2844 生成特殊数字的最少操作 #2761 和等于目标值的质数对 #2928 给小朋友们分糖果 I