#   Count Symmetric Integers
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-symmetric-integers)
Canonical: https://scaleengineer.com/dsa/problems/count-symmetric-integers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
---
## 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]`.

**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`

# Approaches
## Brute-Force Iteration
This approach involves iterating through each number in the given range `[low, high]` and, for each number, performing a check to see if it meets the criteria for being a symmetric integer. It is the most straightforward and intuitive way to solve the problem.
**Time:** O((high - low) * log(high)) - The loop runs `high - low + 1` times. Inside the loop, checking a number involves converting it to a string and iterating through its digits, which takes time proportional to the number of digits, i.e., `O(log(high))`. · **Space:** O(log(high)) - The space required is dominated by the storage for the string representation of the number being checked. The number of digits in `high` is proportional to `log10(high)`.
**Pros:** Simple to understand and implement.; Requires minimal memory (space complexity is very low).
**Cons:** Inefficient if the function is called multiple times with different ranges, as it re-computes the result for each number every time.; Slower than precomputation-based approaches for the given constraints.
### Explanation
We start by initializing a counter variable `count` to zero. Then, we iterate through every integer from `low` to `high`, inclusive. For each integer, we call a helper function, `isSymmetric`, to determine if it's symmetric.

Inside the `isSymmetric` helper function:
1. The integer is first converted to its string representation.
2. We check the length of the string. According to the problem definition, numbers with an odd number of digits are never symmetric, so we immediately return `false` if the length is odd.
3. If the length is even, we proceed to calculate two sums: the sum of the digits in the first half of the string and the sum of the digits in the second half.
4. We compare these two sums. If they are equal, the number is symmetric, and the function returns `true`. Otherwise, it returns `false`.

Back in the main loop, if the helper function returns `true`, we increment our `count`. After checking all numbers in the range, the final value of `count` is the answer.

```java
class Solution {
    public int countSymmetricIntegers(int low, int high) {
        int count = 0;
        for (int i = low; i <= high; i++) {
            if (isSymmetric(i)) {
                count++;
            }
        }
        return count;
    }

    private boolean isSymmetric(int num) {
        String s = Integer.toString(num);
        int n = s.length();
        if (n % 2 != 0) {
            return false;
        }

        int mid = n / 2;
        int sumFirstHalf = 0;
        for (int i = 0; i < mid; i++) {
            sumFirstHalf += s.charAt(i) - '0';
        }

        int sumSecondHalf = 0;
        for (int i = mid; i < n; i++) {
            sumSecondHalf += s.charAt(i) - '0';
        }

        return sumFirstHalf == sumSecondHalf;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Loop through each integer `i` from `low` to `high`.
- For each `i`, check if it is a symmetric integer.
  - Convert the integer `i` to a string `s`.
  - Get the length of the string, `n`.
  - If `n` is odd, the number is not symmetric.
  - If `n` is even, calculate the sum of the first `n/2` digits and the sum of the last `n/2` digits.
  - If the sums are equal, the number is symmetric.
- If the number is symmetric, increment the `count`.
- After the loop finishes, return the `count`.

## Precomputation with Prefix Sums
This approach optimizes the query time by pre-calculating the results for all possible numbers up to the constraint limit (`10000`). By using a prefix sum array, we can answer any query for a range `[low, high]` in constant time. This is highly effective in scenarios where the function might be called multiple times.
**Time:** Precomputation: O(N * log N), Query: O(1) - There is a one-time setup cost of `O(N * log N)` where N is 10000. Each subsequent query is answered in constant time. · **Space:** O(N) - Where N is the maximum value of `high` (10000). We need an array of this size to store the prefix sums.
**Pros:** Extremely fast query time, O(1).; Highly efficient for multiple calls to the function with different ranges.
**Cons:** Requires more memory to store the precomputed array.; Incurs an initial setup cost, which might be a disadvantage if the function is only ever called once on a very small range.
### Explanation
The key idea is to trade space for time. We perform a one-time computation to build a data structure that allows for instant lookups. Given the constraint `high <= 10000`, this is very feasible.

**Precomputation Step:**
We use a static initializer block, which runs only once when the class is loaded. Inside this block:
1. We create an integer array `prefixCount` of size 10001.
2. We iterate from `i = 1` to 10000. For each `i`, we update `prefixCount[i]`. The value is `prefixCount[i-1]` plus an additional 1 if the number `i` is symmetric.
3. To check if `i` is symmetric, we use the same logic as the brute-force method (convert to string, check length, sum halves).

After this block executes, `prefixCount[k]` will hold the total number of symmetric integers in the range `[1, k]`.

**Query Step:**
When the `countSymmetricIntegers(low, high)` method is called, the `prefixCount` array is already populated. The number of symmetric integers in the range `[low, high]` is simply the total count up to `high` minus the total count up to `low - 1`. This is a single subtraction: `prefixCount[high] - prefixCount[low - 1]`.

```java
class Solution {
    private static final int MAX_VAL = 10000;
    private static final int[] prefixCount = new int[MAX_VAL + 1];

    // Static initializer block to precompute the counts
    static {
        for (int i = 1; i <= MAX_VAL; i++) {
            prefixCount[i] = prefixCount[i - 1];
            if (isSymmetric(i)) {
                prefixCount[i]++;
            }
        }
    }

    private static boolean isSymmetric(int num) {
        String s = Integer.toString(num);
        int n = s.length();
        if (n % 2 != 0) {
            return false;
        }
        int mid = n / 2;
        int sum1 = 0;
        for (int i = 0; i < mid; i++) {
            sum1 += s.charAt(i) - '0';
        }
        int sum2 = 0;
        for (int i = mid; i < n; i++) {
            sum2 += s.charAt(i) - '0';
        }
        return sum1 == sum2;
    }

    public int countSymmetricIntegers(int low, int high) {
        return prefixCount[high] - prefixCount[low - 1];
    }
}
```
### Algorithm
#### One-time Setup:
- Create a prefix sum array, `prefixCount`, of size `10001`.
- Iterate from `i = 1` to `10000`.
- For each `i`, calculate `prefixCount[i]` as `prefixCount[i-1]` plus 1 if `i` is symmetric, or `prefixCount[i-1]` if it's not.
- The check for whether `i` is symmetric is the same as in the brute-force approach.

#### Query Phase:
- To find the count of symmetric integers in `[low, high]`, compute `prefixCount[high] - prefixCount[low - 1]`.

# Solutions
### CSharp

```csharp
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;
    }
}
```

### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

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

```