2843. Count Symmetric Integers
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:
- Convert the integer to a string, so it's easier to split and work with individual digits.
- 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 returnFalse
. - If the length is even, find the midpoint (
n
) and then split the string into two halves. - Convert each digit from both halves back to integers and sum them up separately.
- Compare the two sums. If they are equal,
f
will returnTrue
, 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.
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:
-
Helper Function
f(x: int) -> bool
: This function takes an integerx
and returns a boolean indicating whetherx
is a symmetric number.- It first converts the integer
x
into a strings
, making it easier to handle individual digits. - The function immediately checks if the length of
s
is odd. If so, it returnsFalse
because symmetric numbers must have an even number of digits. - It calculates
n
, which is half the length of the strings
, to divide the number into its two parts. - It then takes the first
n
digits and the secondn
digits, converts each digit to an integer usingmap
, and calculates their sums. - Lastly,
f
compares the two sums and returnsTrue
if they are equal (symmetric) orFalse
if not.
- It first converts the integer
-
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 functionf
to each integerx
in the range fromlow
tohigh
(inclusive). - The
for
loop is enclosed in thesum()
function, which adds up all theTrue
values (eachTrue
is equivalent to1
in Python) returned byf
, 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.
- It uses a
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
:
- Convert it to a string: "1200"
- The length of the string is 4, which is even, so it's possible for the number to be symmetric.
- Calculate the midpoint:
n = len("1200") / 2 = 2
- Split the string into two parts: "12" and "00"
- Convert the digits and calculate the sums: sum of "12" = 1 + 2 = 3, sum of "00" = 0 + 0 = 0
- Compare the sums: since 3 is not equal to 0,
f(1200)
returnsFalse
. Hence, 1200 is not a symmetric number.
Moving on to the number 1301
:
- Convert it to a string: "1301"
- The length of the string is 4, which is even, so it's possible for the number to be symmetric.
- Calculate the midpoint:
n = len("1301") / 2 = 2
- Split the string into two parts: "13" and "01"
- Convert the digits and calculate the sums: sum of "13" = 1 + 3 = 4, sum of "01" = 0 + 1 = 1
- Compare the sums: since 4 is not equal to 1,
f(1301)
returnsFalse
. 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
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 takesO(d)
time, whered
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 takeO(d)
time for each half, totaling toO(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 off(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.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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 Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.