Question

2843. 统计对称整数的数目

English Version

题目描述

给你两个正整数 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 <= 104

解法

方法一：枚举

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

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

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

class Solution {
  public int countSymmetricIntegers(int low, int high) {
    int ans = 0;
    for (int x = low; x <= high; ++x) {
      ans += f(x);
    }
    return ans;
  }

  private int f(int x) {
    String s = "" + x;
    int n = s.length();
    if (n % 2 == 1) {
      return 0;
    }
    int a = 0, b = 0;
    for (int i = 0; i < n / 2; ++i) {
      a += s.charAt(i) - '0';
    }
    for (int i = n / 2; i < n; ++i) {
      b += s.charAt(i) - '0';
    }
    return a == b ? 1 : 0;
  }
}

class Solution {
public:
  int countSymmetricIntegers(int low, int high) {
    int ans = 0;
    auto f = [](int x) {
      string s = to_string(x);
      int n = s.size();
      if (n & 1) {
        return 0;
      }
      int a = 0, b = 0;
      for (int i = 0; i < n / 2; ++i) {
        a += s[i] - '0';
        b += s[n / 2 + i] - '0';
      }
      return a == b ? 1 : 0;
    };
    for (int x = low; x <= high; ++x) {
      ans += f(x);
    }
    return ans;
  }
};

func countSymmetricIntegers(low int, high int) (ans int) {
  f := func(x int) int {
    s := strconv.Itoa(x)
    n := len(s)
    if n&1 == 1 {
      return 0
    }
    a, b := 0, 0
    for i := 0; i < n/2; i++ {
      a += int(s[i] - '0')
      b += int(s[n/2+i] - '0')
    }
    if a == b {
      return 1
    }
    return 0
  }
  for x := low; x <= high; x++ {
    ans += f(x)
  }
  return
}

function countSymmetricIntegers(low: number, high: number): number {
  let ans = 0;
  const f = (x: number): number => {
    const s = x.toString();
    const n = s.length;
    if (n & 1) {
      return 0;
    }
    let a = 0;
    let b = 0;
    for (let i = 0; i < n >> 1; ++i) {
      a += Number(s[i]);
      b += Number(s[(n >> 1) + i]);
    }
    return a === b ? 1 : 0;
  };
  for (let x = low; x <= high; ++x) {
    ans += f(x);
  }
  return ans;
}