Skip to content

2843. Count Symmetric Integers

SourceWeekly Contest 361 Q1DifficultyEasyRating1269

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:

  • 1 <= low <= high <= 104

Solutions

Solution 1: Enumeration

Thinking

With \(\textit{high}\le 10^4\), every integer in the range can be tested: even length and equal digit sums on the two halves. Digit DP is unnecessary.

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

The time complexity is \(O(n \log m)\), and the space complexity is \(O(\log m)\), where \(n\) is the number of integers in the range \([\textit{low}, \textit{high}]\), and \(m\) is the maximum integer given in the problem.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
    }
}

Comments