Problem

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].

Examples

Example 1:

1
2
3

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:

1
2
3

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

Solution

Method 1 - Iteration

  1. Symmetric Checks:
    • A number is symmetric if it has an even number of digits (2 * n digits).
    • Split the digits into two halves, sum them, and check if they are equal.
    • Numbers with odd digits are skipped.
  2. Steps in the Solution:
    • Iterate through all integers in the range [low, high].
    • Convert each integer to a string, check if it has an even number of digits.
    • For numbers with even digits, compute the sum of the first n digits and the last n digits to determine symmetry.
    • Count the symmetric numbers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {

    public int countSymmetricIntegers(int low, int high) {
        int ans = 0;
        for (int x = low; x <= high; x++) {
            String s = String.valueOf(x);
            if (s.length() % 2 == 0) {
                int n = s.length() / 2;
                int sum1 = 0, sum2 = 0;
                for (int i = 0; i < n; i++) {
                    sum1 += s.charAt(i) - '0';
                    sum2 += s.charAt(i + n) - '0';
                }
                if (sum1 == sum2) {
                    ans++;
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def count_symmetric_integers(self, low: int, high: int) -> int:
        ans = 0
        for x in range(low, high + 1):
            s = str(x)
            if len(s) % 2 == 0:
                n = len(s) // 2
                if sum(map(int, s[:n])) == sum(map(int, s[n:])):
                    ans += 1
        return ans

Complexity

  • ⏰ Time complexity: O((high-low+1) * d)
    • We iterate through all numbers in [low, high].
    • For each number with d digits, we compute sums, which takes O(d).
  • 🧺 Space complexity: O(d). In python, due to string conversion and slicing. In java, due to string storage during the iteration.