Description
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].
Example 1:
Input: low = 1, high = 100
Output: 9
Explanation: 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
Explanation: There are 4 symmetric integers between 1200 and 1230: 1203, 1212, 1221, and 1230.
Constraints:
Solutions
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.
The time complexity is O(n × log m), and the space complexity is O(log m). Here, n is the number of integers in the range [low, high], and m is the maximum integer given in the problem.
PythonJavaC++GoTypeScriptRustC#
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))(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
impl Solution {
pub fn count_symmetric_integers(low: i32, high: i32) -> i32 {
let mut ans = 0;
for x in low..=high {
ans += Self::f(x);
}
ans
}
fn f(x: i32) -> i32 {
let s = x.to_string();
let n = s.len();
if n % 2 == 1 {
return 0;
}
let bytes = s.as_bytes();
let mut a = 0;
let mut b = 0;
for i in 0..n / 2 {
a += (bytes[i] - b'0') as i32;
}
for i in n / 2..n {
b += (bytes[i] - b'0') as i32;
}
if a == b { 1 } else { 0 }
}
}(code-box)
public 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.ToString();
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[i] - '0';
}
for (int i = n / 2; i < n; ++i) {
b += s[i] - '0';
}
return a == b ? 1 : 0;
}
}(code-box)
