2843. Count Symmetric Integers

EasyMathEnumeration
Leetcode Link

Problem Description

The problem provides us with two positive integers, low and high. We need to determine the count of symmetric integers within this inclusive range. An integer x is considered symmetric if it has an even number of digits (2 * n), and the sum of the first half of its digits (n digits) is equal to the sum of the second half (n digits). For instance, the number 123321 is symmetric because the sum of 123 is equal to the sum of 321. Integers with odd numbers of digits cannot be symmetric by definition provided. Our goal is to calculate how many symmetric numbers exist between low and high, inclusive.

Intuition

The problem at hand is an excellent example of brute force technique where we iterate over each number within the range provided and check if it is symmetric.

The intuition behind the provided solution starts with defining what a symmetric number is and understanding that symmetry is only possible with an even number of digits. Hence, numbers with an odd number of digits can be immediately discarded as they can never be symmetric.

Given the definition of symmetry, the next logical step is to split the number into two equal parts and compare their digit sums. To achieve this, for each number within the given range:

  1. Convert the integer to a string, so it's easier to split and work with individual digits.
  2. Check if the length of the string (representing the number) is odd. If it's odd, this number cannot be symmetric, and the function f should return False.
  3. If the length is even, find the midpoint (n) and then split the string into two halves.
  4. Convert each digit from both halves back to integers and sum them up separately.
  5. Compare the two sums. If they are equal, f will return True, indicating that the number is symmetric; otherwise, False.

Having the function f ready, the next step is to apply it to each number within the low to high range. The solution approach uses Python's sum() function in a generator expression to count how many times f returns True for numbers in the range. The count of True returns is the count of symmetric numbers, which is what the countSymmetricIntegers method finally returns.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Solution Approach

The solution for this problem uses a simple brute force algorithm to find all symmetric numbers between two integers, low and high. This is achieved using a helper function f to check each number's symmetry and a main method that iterates through the range, using a generator expression to count the symmetric numbers.

Let's walk through the key components of the implementation:

  1. Helper Function f(x: int) -> bool: This function takes an integer x and returns a boolean indicating whether x is a symmetric number.

    • It first converts the integer x into a string s, making it easier to handle individual digits.
    • The function immediately checks if the length of s is odd. If so, it returns False because symmetric numbers must have an even number of digits.
    • It calculates n, which is half the length of the string s, to divide the number into its two parts.
    • It then takes the first n digits and the second n digits, converts each digit to an integer using map, and calculates their sums.
    • Lastly, f compares the two sums and returns True if they are equal (symmetric) or False if not.

  2. Main Method countSymmetricIntegers(low: int, high: int) -> int: This is where the range of numbers is processed.

    • It uses a for loop within a generator expression (f(x) for x in range(low, high + 1)) to apply the helper function f to each integer x in the range from low to high (inclusive).
    • The for loop is enclosed in the sum() function, which adds up all the True values (each True is equivalent to 1 in Python) returned by f, thus counting the number of symmetric numbers.
    • The sum, which represents the count of symmetric numbers in the given range, is then returned as the output.

This solution approach does not use any complex data structures as the problem is more focused on digit manipulation and comparison rather than data manipulation. By converting the numbers to strings, it takes advantage of Python's string indexing and slicing capabilities to easily and intuitively work with numerical halves. The concise design of the solution with a separate function for symmetry check keeps the code clean and readable.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many times is a tree node visited in a depth first search?

Example Walkthrough

Let's consider a small range of numbers to illustrate the solution approach, specifically the range from low = 1200 to high = 1301.

We need to check each number within this range to see if it is a symmetric integer. According to the problem statement, for an integer to be symmetric, it must have an even number of digits, and the sum of the first half of its digits must be equal to the sum of the second half.

Let's start with the first number in the range, 1200:

  1. Convert it to a string: "1200"
  2. The length of the string is 4, which is even, so it's possible for the number to be symmetric.
  3. Calculate the midpoint: n = len("1200") / 2 = 2
  4. Split the string into two parts: "12" and "00"
  5. Convert the digits and calculate the sums: sum of "12" = 1 + 2 = 3, sum of "00" = 0 + 0 = 0
  6. Compare the sums: since 3 is not equal to 0, f(1200) returns False. Hence, 1200 is not a symmetric number.

Moving on to the number 1301:

  1. Convert it to a string: "1301"
  2. The length of the string is 4, which is even, so it's possible for the number to be symmetric.
  3. Calculate the midpoint: n = len("1301") / 2 = 2
  4. Split the string into two parts: "13" and "01"
  5. Convert the digits and calculate the sums: sum of "13" = 1 + 3 = 4, sum of "01" = 0 + 1 = 1
  6. Compare the sums: since 4 is not equal to 1, f(1301) returns False. Hence, 1301 is not a symmetric number.

None of the numbers from 1200 to 1301 are symmetric since we won't find any number in that range satisfying the symmetric condition. Thus, when the countSymmetricIntegers(1200, 1301) method is called, it will iterate through the range using the helper function f and the sum of the number of symmetric integers will be zero as none of the numbers will return True.

If we carefully observe, the smallest number that could potentially be symmetric in this range is 1210 because its digit sum for the first half "12" is 1 + 2 = 3, which is equal to the digit sum for the second half "10", which is 1 + 0 = 1, but since 3 is not equal to 1, it is also not symmetric. Any number in this range that has a zero cannot be symmetric as any other digit's sum will be more than zero making it impossible to be symmetric. So, it saves us the computational effort of checking each number by understanding the inherent properties of the numbers within the given range.

Solution Implementation

1class Solution:
2    def count_symmetric_integers(self, low: int, high: int) -> int:
3        # Helper function to check if an integer is symmetric
4        # An integer is symmetric if sum of the first half of its digits equals sum of the second half,
5        # and only the even-length numbers can be symmetric by this definition.
6        def is_symmetric(num: int) -> bool:
7            str_num = str(num)
8            # Check for even length
9            if len(str_num) % 2 == 1:
10                return False
11            half_length = len(str_num) // 2
12            # Calculate sum of the first half and the second half of the digits
13            first_half_sum = sum(map(int, str_num[:half_length]))
14            second_half_sum = sum(map(int, str_num[half_length:]))
15            # Check if both halves have equal sum
16            return first_half_sum == second_half_sum
17
18        # Calculate the number of symmetric integers within the given range
19        symmetric_count = sum(is_symmetric(num) for num in range(low, high + 1))
20        return symmetric_count
21
1class Solution {
2    // Method to count symmetric integers within a given range
3    public int countSymmetricIntegers(int low, int high) {
4        int count = 0; // Initialize count to keep track of symmetric integers
5        // Iterate through the range from low to high
6        for (int num = low; num <= high; ++num) {
7            // Add the result of the isSymmetric helper function to the count
8            count += isSymmetric(num);
9        }
10        return count; // Return the total count of symmetric integers
11    }
12
13    // Helper method to determine if an integer is symmetric
14    private int isSymmetric(int num) {
15        String numStr = Integer.toString(num); // Convert the integer to a string representation
16        int length = numStr.length(); // Calculate the length of the string
17        if (length % 2 == 1) { // If the length of the number is odd, it is not symmetric
18            return 0;
19        }
20        int firstHalfSum = 0, secondHalfSum = 0; // Initialize sums for both halves
21        // Sum the digits in the first half of the string
22        for (int i = 0; i < length / 2; ++i) {
23            firstHalfSum += numStr.charAt(i) - '0'; // Convert char to int and add to the sum
24        }
25        // Sum the digits in the second half of the string
26        for (int i = length / 2; i < length; ++i) {
27            secondHalfSum += numStr.charAt(i) - '0'; // Convert char to int and add to the sum
28        }
29        // If the sums of both halves match, the number is symmetric
30        return firstHalfSum == secondHalfSum ? 1 : 0;
31    }
32}
33
1class Solution {
2public:
3    // Function to count the symmetric integers between `low` and `high`.
4    int countSymmetricIntegers(int low, int high) {
5        // Initialize the answer counter.
6        int count = 0;
7        // Define the lambda function to check if an integer is symmetric.
8        auto isSymmetric = [](int num) {
9            // Convert the number to a string.
10            string numStr = to_string(num);
11            // Get the number of digits in the string.
12            int length = numStr.size();
13            // Check if the number of digits is odd. If it is, return 0 immediately.
14            if (length % 2 == 1) {
15                return 0;
16            }
17            // Initialize the sums of the first half and second half of the digits.
18            int sumFirstHalf = 0, sumSecondHalf = 0;
19            // Iterate over the first half and second half digits and sum them up.
20            for (int i = 0; i < length / 2; ++i) {
21                sumFirstHalf += numStr[i] - '0';
22                sumSecondHalf += numStr[length / 2 + i] - '0';
23            }
24            // Return 1 if the sums are equal, else return 0.
25            return sumFirstHalf == sumSecondHalf ? 1 : 0;
26        };
27        // Iterate over the range of numbers from `low` to `high`.
28        for (int num = low; num <= high; ++num) {
29            // Increase the counter if the current number is symmetric.
30            count += isSymmetric(num);
31        }
32        // Return the final count of symmetric integers.
33        return count;
34    }
35};
36
1function countSymmetricIntegers(low: number, high: number): number {
2    let count = 0; // Initialize the counter for symmetric integers
3
4    // Define a helper function to check if a number is symmetric
5    // In this context, a symmetric number is defined as having an even number of digits,
6    // with the sum of the first half of the digits equal to the sum of the second half
7    const isSymmetric = (num: number): number => {
8        const strNum = num.toString(); // Convert the number to a string
9        const length = strNum.length; // Get the length of the string
10
11        // If the number of digits is odd, it can't be symmetric
12        if (length & 1) {
13            return 0;
14        }
15
16        let firstHalfSum = 0; // Sum of the first half of digits
17        let secondHalfSum = 0; // Sum of the second half of digits
18
19        // Calculate the sums for the first and the second halves of the string
20        for (let i = 0; i < length / 2; ++i) {
21            firstHalfSum += Number(strNum[i]); // Add the digit to the first half's sum
22            secondHalfSum += Number(strNum[length / 2 + i]); // Add the digit to the second half's sum
23        }
24
25        // If both halves have the same sum, return 1 indicating a symmetric number
26        return firstHalfSum === secondHalfSum ? 1 : 0;
27    };
28
29    // Loop through the range from 'low' to 'high' to count symmetric numbers
30    for (let num = low; num <= high; ++num) {
31        count += isSymmetric(num); // Add the result of isSymmetric to the count
32    }
33
34    return count; // Return the total count of symmetric numbers
35}
36
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Time and Space Complexity

Time Complexity

The time complexity of the given code can be evaluated by looking at the number of operations it performs in relation to the input range low to high.

We perform a loop from low to high, inclusive. Therefore, the number of iterations is (high - low + 1).

Within each iteration, we do the following:

  • Convert the number x to a string, which takes O(d) time, where d is the number of digits in the number.
  • Check the length of the string; this is a constant time operation, O(1).
  • Calculate the half-length of the string, which is also a constant time operation, O(1).
  • Split the string and sum the digits of both halves. Since each half of the string has d/2 digits, the map and sum operations together take O(d) time for each half, totaling to O(d) for the entire string.

Since each digit in the input number can be processed independently, we can consider d to be O(log10(x)), where x is a number in the given range. This is because the number of digits in a number is proportional to the logarithm of the number itself.

Therefore, for each iteration, we spend O(log10(x)) time, and since we do this for each x in the range from low to high, the overall time complexity is O((high - low + 1) * log10(high)), assuming high has the maximum number of digits within the range.

Space Complexity

Regarding space complexity, the code uses only a constant amount of extra space, which is independent of the input size. It includes:

  • Storage for temporary variables such as s, n, and the return value of f(x).
  • The space needed for the integer-to-string conversion, which at most storage for a string representation of high.

As the storage does not grow with the size of the input range, the space complexity remains constant O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used in a depth first search?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫