Problem Informations

Problem Index: 2843
Problem Link: Count Symmetric Integers
Topics: Math, Enumeration

Problem 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 \leq \text{{low}} \leq \text{{high}} \leq 10^4$

Intuition

The problem requires identifying and counting “symmetric” integers in a given range. A “symmetric” integer is defined as having an even number of digits where the sum of the first half of its digits equals the sum of the second half. The challenge lies in efficiently determining which numbers within a specified range exhibit this property. Our initial thoughts involve systematically evaluating every integer within the given bounds, analyzing the digit structure of each, and calculating the necessary sums to verify symmetry.

Approach

The approach to solving this problem involves iterating through each integer in the range [low, high] and checking if it meets the criteria for symmetry. The solution employs the following steps:

Helper Function isSymmetric:
- This function takes an integer num and determines whether it is symmetric.
- Determine Length: Calculate the total number of digits in num using the formula length = log10(num) + 1.
- Check Evenness: Symmetric numbers must have an even number of digits. If the length is odd, return false immediately, as such numbers cannot be symmetric.
- Calculate Sums: For an even-length num, the steps are as follows:
  - Initialize a sum variable to zero.
  - Second Half Sum: Extract and sum the last n digits (where n is half the length of num). This is achieved by iteratively taking the remainder of num when divided by 10, adding it to sum, and then dividing num by 10.
  - First Half Sum: Subtract the sum of the first n digits from the previously computed sum using the same iterative technique. If the resulting total sum is zero, then the sums of the two halves are equal, indicating symmetry.
- Return true if sum is zero and false otherwise.
Main Function countSymmetricIntegers:
- Initialize a counter symmetricCount to zero.
- Iterate through each integer i in the range [low, high].
  - Use the helper function isSymmetric to check each number:
    - If isSymmetric(i) returns true, increment symmetricCount.
- Finally, return the value of symmetricCount which represents the total number of symmetric integers found in the specified range.

This straightforward, brute-force approach ensures that all integers in the given range are evaluated for symmetry, leveraging the helper function to simplify and encapsulate the logic of determining symmetry based on the digits’ sum.

Code

C++

class Solution {
public:
    // Function to check if a given number is symmetric
    bool isSymmetric(int num) {
        int length = log10(num) + 1; // Calculate length of the number
        int sum = 0;
        
        // If the length is odd, the number can't be symmetric
        if (length % 2 != 0) 
            return false;
        
        // Calculate the sum of the last n digits
        for (int i = 0; i < length / 2; i++) {
            sum += num % 10;
            num /= 10;
        }
        
        // Subtract the sum of the first n digits
        for (int i = 0; i < length / 2; i++) {
            sum -= num % 10;
            num /= 10;
        }
        
        // If the sums are equal, the number is symmetric
        return sum == 0;
    }
    
    // Function to count symmetric integers in a given range [low, high]
    int countSymmetricIntegers(int low, int high) {
        int symmetricCount = 0;

        // Iterate over each number in the given range
        for (int i = low; i <= high; i++) {
            // Increment count if the number is symmetric
            if (isSymmetric(i)) 
                symmetricCount++;
        }

        return symmetricCount; // Return the total count of symmetric numbers
    }
};

Python

class Solution:
    # Function to check if a given number is symmetric
    def isSymmetric(self, num: int) -> bool:
        length = int(log10(num)) + 1  # Calculate length of the number
        sum = 0
        
        # If the length is odd, the number can't be symmetric
        if length % 2 != 0:
            return False
        
        # Calculate the sum of the last n digits
        for i in range(length // 2):
            sum += num % 10
            num //= 10
        
        # Subtract the sum of the first n digits
        for i in range(length // 2):
            sum -= num % 10
            num //= 10
        
        # If the sums are equal, the number is symmetric
        return sum == 0
    
    # Function to count symmetric integers in a given range [low, high]
    def countSymmetricIntegers(self, low: int, high: int) -> int:
        symmetricCount = 0

        # Iterate over each number in the given range
        for i in range(low, high + 1):
            # Increment count if the number is symmetric
            if self.isSymmetric(i):
                symmetricCount += 1

        return symmetricCount  # Return the total count of symmetric numbers

Complexity

Time complexity: $O(n \cdot d)$
The time complexity of the countSymmetricIntegers function is $O(n \cdot d)$, where $n$ is the difference between high and low (i.e., $n = \text{{high}} - \text{{low}} + 1$) and $d$ is the number of digits in the largest number within this range. This is because for each number in the range [low, high], the isSymmetric function is called, which processes up to $d/2$ digits twice—once for summing the last $n$ digits and once for subtracting the first $n$ digits. Therefore, each call to isSymmetric takes $O(d)$ time, and there are $n$ such calls, leading to a total time complexity of $O(n \cdot d)$.
Space complexity: $O(1)$
The space complexity is $O(1)$ because the only extra space used is for a few integer variables, and this does not depend on the size of the input. The function does not utilize any data structures that scale with the input size.

CS Note
中

Leetcode 2843. Count Symmetric Integers