Count Symmetric Integers

Easy

#2542Time: 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)`.

Patterns

Math Enumeration

Prompt

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 <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

The integer is first converted to its string representation.
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.
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.
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.

1class Solution {2    public int countSymmetricIntegers(int low, int high) {3        int count = 0;4        for (int i = low; i <= high; i++) {5            if (isSymmetric(i)) {6                count++;7            }8        }9        return count;10    }11 12    private boolean isSymmetric(int num) {13        String s = Integer.toString(num);14        int n = s.length();15        if (n % 2 != 0) {16            return false;17        }18 19        int mid = n / 2;20        int sumFirstHalf = 0;21        for (int i = 0; i < mid; i++) {22            sumFirstHalf += s.charAt(i) - '0';23        }24 25        int sumSecondHalf = 0;26        for (int i = mid; i < n; i++) {27            sumSecondHalf += s.charAt(i) - '0';28        }29 30        return sumFirstHalf == sumSecondHalf;31    }32}

Complexity

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

Trade-offs

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.

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.

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

Walkthrough

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:

We create an integer array prefixCount of size 10001.
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.
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].

1class Solution {2    private static final int MAX_VAL = 10000;3    private static final int[] prefixCount = new int[MAX_VAL + 1];4 5    // Static initializer block to precompute the counts6    static {7        for (int i = 1; i <= MAX_VAL; i++) {8            prefixCount[i] = prefixCount[i - 1];9            if (isSymmetric(i)) {10                prefixCount[i]++;11            }12        }13    }14 15    private static boolean isSymmetric(int num) {16        String s = Integer.toString(num);17        int n = s.length();18        if (n % 2 != 0) {19            return false;20        }21        int mid = n / 2;22        int sum1 = 0;23        for (int i = 0; i < mid; i++) {24            sum1 += s.charAt(i) - '0';25        }26        int sum2 = 0;27        for (int i = mid; i < n; i++) {28            sum2 += s.charAt(i) - '0';29        }30        return sum1 == sum2;31    }32 33    public int countSymmetricIntegers(int low, int high) {34        return prefixCount[high] - prefixCount[low - 1];35    }36}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1public class Solution {2    public int CountSymmetricIntegers(int low, int high) {3        int ans = 0;4        for (int x = low; x <= high; ++x) {5            ans += f(x);6        }7        return ans;8    }9    private int f(int x) {10        string s = x.ToString();11        int n = s.Length;12        if (n % 2 == 1) {13            return 0;14        }15        int a = 0, b = 0;16        for (int i = 0; i < n / 2; ++i) {17            a += s[i] - '0';18        }19        for (int i = n / 2; i < n; ++i) {20            b += s[i] - '0';21        }22        return a == b ? 1 : 0;23    }24}

1class Solution {2public3  int countSymmetricIntegers(int low, int high) {4    int ans = 0;5    for (int x = low; x <= high; ++x) {6      ans += f(x);7    }8    return ans;9  }10private11  int f(int x) {12    String s = "" + x;13    int n = s.length();14    if (n % 2 == 1) {15      return 0;16    }17    int a = 0, b = 0;18    for (int i = 0; i < n / 2; ++i) {19      a += s.charAt(i) - '0';20    }21    for (int i = n / 2; i < n; ++i) {22      b += s.charAt(i) - '0';23    }24    return a == b ? 1 : 0;25  }26}

1class Solution {2public:3  int countSymmetricIntegers(int low, int high) {4    int ans = 0;5    auto f = [](int x) {6      string s = to_string(x);7      int n = s.size();8      if (n & 1) {9        return 0;10      }11      int a = 0, b = 0;12      for (int i = 0; i < n / 2; ++i) {13        a += s[i] - '0';14        b += s[n / 2 + i] - '0';15      }16      return a == b ? 1 : 0;17    };18    for (int x = low; x <= high; ++x) {19      ans += f(x);20    }21    return ans;22  }23};

1class Solution:2    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))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem