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 <= 104This approach involves checking each integer in the range [low, high] to determine if it is symmetric. For each number, split its digits into two halves and check if their sums are equal.
For a number with 2n digits, calculate if the sum of the first n digits equals the sum of the last n digits. If equal, count it as a symmetric integer.
This C solution first converts the number to a string to analyze its digits. By iterating over half of the string and computing sums for both halves, it determines if a number is symmetric. The main function calls this helper function for every number in the range to count symmetric numbers.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N * D), where N is the number of integers in the range and D is the number of digits in the number, due to conversion and summation.
Space Complexity: O(D), due to storage of the string representing the number.
This approach avoids checking each integer but analyzes digits for patterns. It constructs symmetric numbers by iterating over possible sums for halves within digit constraints. This quicker method leverages properties of digit sums and avoids visiting each candidate.
This solution in C iterates through potential digits, treating any pair of mirrored digits in a number. It calculates potential numbers by reconstructing them using two digits at even positions and mirrors them. It keeps track of valid symmetric numbers within the range.
C++
Java
Python
C#
JavaScript
Time Complexity: O(D^2), due to the nesting of two loops across potential digit values.
Space Complexity: O(1), no additional storage proportional to input size is used.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(N * D), where N is the number of integers in the range and D is the number of digits in the number, due to conversion and summation. Space Complexity: O(D), due to storage of the string representing the number. |
| Digit Analysis Approach | Time Complexity: O(D^2), due to the nesting of two loops across potential digit values. Space Complexity: O(1), no additional storage proportional to input size is used. |
Count Symmetric Integers | 2 Detailed Approaches | Leetcode 2843 | codestorywithMIK • codestorywithMIK • 5,769 views views
Watch 9 more video solutions →Practice Count Symmetric Integers with our built-in code editor and test cases.
Practice on FleetCode