Count Symmetric Integers solution and explanation
Google
9 more videos on this problem
Count Symmetric Integers | 2 Detailed Approaches | Leetcode 2843 | codestorywithMIKcodestorywithMIK · 18:58 · 6K views
LeetCode 2843. Count Symmetric Integers | Made Easy! 🔥🍥Code Crusaders · 4:01 · 955 views
LeetCode 2843 Count Symmetric Integers | Math | Enumeration | GoogleCode Harmony · 17:25 · 867 views
Leetcode 2843 Count Symmetric IntegersTech Diet · 4:02 · 809 views
2843. Count Symmetric Integers | Maths | LeetcodeRapid Syntax · 7:04 · 707 views
2843. Count Symmetric Integers (Leetcode Easy)Programming Live with Larry · 3:59 · 673 views
Count Symmetric Integers | LeetCode 2843 | Enumeration | Java Code | Developer CoderDeveloper Coder · 11:06 · 100 views
2843. Count Symmetric Integers | Leetcode Daily - PythonLeetcode Daily · 8:27 · 88 views
Count Symmetric Integers - Leetcode 2843 - PythonTim Huang · 4:09 · 71 views
LeetCode 2843 | Count Symmetric Integers | Easy Explanation | JavaTheCodeCombat · 4:27 · 69 views
The problem
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 <= 104
Approach overview
Problem Overview: You are given two integers low and high. Count how many numbers in this range are symmetric. A number is symmetric if it has an even number of digits and the sum of the first half of digits equals the sum of the second half.
Approach 1: Brute Force Enumeration (Time: O(n * d), Space: O(1))
Iterate through every integer from low to high. Convert the number to a string (or extract digits using division). If the digit count is odd, skip it immediately. Otherwise split the digits into two halves, compute the sum of each half, and compare them. If the sums match, increment the answer.
This approach relies purely on enumeration, making it straightforward to implement. The cost comes from processing digits for every number in the range. With d representing the number of digits, the complexity becomes O(n * d). Given the constraint that numbers are at most 5 digits, this runs comfortably fast.
Approach 2: Digit Analysis (Time: O(n), Space: O(1))
Instead of handling digits generically, analyze the possible digit lengths directly. Within the problem constraints, only 2-digit and 4-digit numbers can be symmetric. For 2-digit numbers, the condition reduces to a == b. For 4-digit numbers abcd, the rule becomes a + b == c + d.
Iterate through the range and apply these checks using arithmetic operations such as division and modulo to extract digits. This avoids string conversion and minimizes per-number work. Each number is checked in constant time, giving overall O(n) time and O(1) space.
This solution uses simple number manipulation techniques from math and systematic range scanning from enumeration. The key insight is recognizing that symmetric numbers only exist for even digit counts and that the comparison reduces to two small digit sums.
Recommended for interviews: Start with the brute force enumeration to demonstrate correctness and clarity. Then optimize with digit analysis by avoiding string conversions and handling only valid digit lengths. Interviewers typically expect the constant-time digit extraction approach since it shows comfort with numeric manipulation and edge-case reasoning.
Approach 1: Brute Force Approach
This 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.
def is_symmetric(num):
str_num = str(num)
length = len(str_num)
if length % 2 != 0:
return False
mid = length // 2
sum1 = sum(int(str_num[i]) for i in range(mid))
sum2 = sum(int(str_num[i]) for i in range(mid, length))
return sum1 == sum2
def count_symmetric_integers(low, high):
count = 0
for i in range(low, high + 1):
if is_symmetric(i):
count += 1
return count
low = 1
high = 100
print(count_symmetric_integers(low, high))public class SymmetricInteger {
public static int countSymmetricIntegers(int low, int high) {
int count = 0;
for (int i = low; i <= high; i++) {
if (isSymmetric(i)) count++;
}
return count;
}
private static boolean isSymmetric(int num) {
String str = Integer.toString(num);
int len = str.length();
if (len % 2 != 0) return false;
int mid = len / 2;
int sum1 = 0, sum2 = 0;
for (int i = 0; i < mid; i++) {
sum1 += str.charAt(i) - '0';
sum2 += str.charAt(i + mid) - '0';
}
return sum1 == sum2;
}
public static void main(String[] args) {
int low = 1, high = 100;
System.out.println(countSymmetricIntegers(low, high));
}
}#include <iostream>
#include <string>
bool is_symmetric(int num) {
std::string str = std::to_string(num);
int len = str.size();
if (len % 2 != 0) return false;
int mid = len / 2;
int sum1 = 0, sum2 = 0;
for (int i = 0; i < mid; i++) {
sum1 += str[i] - '0';
sum2 += str[mid + i] - '0';
}
return sum1 == sum2;
}
int count_symmetric_integers(int low, int high) {
int count = 0;
for (int i = low; i <= high; i++) {
if (is_symmetric(i)) count++;
}
return count;
}
int main() {
int low = 1, high = 100;
std::cout << count_symmetric_integers(low, high) << std::endl;
return 0;
}function isSymmetric(num) {
const str = num.toString();
const len = str.length;
if (len % 2 !== 0) return false;
const mid = len / 2;
let sum1 = 0, sum2 = 0;
for (let i = 0; i < mid; i++) {
sum1 += parseInt(str[i], 10);
sum2 += parseInt(str[i + mid], 10);
}
return sum1 === sum2;
}
function countSymmetricIntegers(low, high) {
let count = 0;
for (let i = low; i <= high; i++) {
if (isSymmetric(i)) count++;
}
return count;
}
console.log(countSymmetricIntegers(1, 100));#include <stdio.h>
#include <string.h>
int is_symmetric(int num) {
char str[10];
sprintf(str, "%d", num);
int len = strlen(str);
if (len % 2 != 0) return 0;
int mid = len / 2;
int sum1 = 0, sum2 = 0;
for (int i = 0; i < mid; i++) {
sum1 += str[i] - '0';
sum2 += str[i + mid] - '0';
}
return sum1 == sum2;
}
int count_symmetric_integers(int low, int high) {
int count = 0;
for (int i = low; i <= high; i++) {
if (is_symmetric(i)) count++;
}
return count;
}
int main() {
int low = 1, high = 100;
printf("%d\n", count_symmetric_integers(low, high));
return 0;
}using System;
public class SymmetricIntegers {
public static int CountSymmetricIntegers(int low, int high) {
int count = 0;
for (int i = low; i <= high; i++) {
if (IsSymmetric(i)) count++;
}
return count;
}
private static bool IsSymmetric(int num) {
string str = num.ToString();
int len = str.Length;
if (len % 2 != 0) return false;
int mid = len / 2;
int sum1 = 0, sum2 = 0;
for (int i = 0; i < mid; i++) {
sum1 += str[i] - '0';
sum2 += str[i + mid] - '0';
}
return sum1 == sum2;
}
public static void Main() {
int low = 1, high = 100;
Console.WriteLine(CountSymmetricIntegers(low, high));
}
}This Python solution applies similar logic for checking symmetrical properties by converting numbers to strings and evaluating whether the sum of the two halves are equal. It counts all such symmetric numbers within the specified range.
Time Complexity: O(N * D), due to checking each number in the range and processing its digits.
Space Complexity: O(D), as digits are stored in a string per calculation.
Approach 2: Digit Analysis Approach
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.
def count_symmetric_integers_by_digits(low, high):
count = 0
for d in (1, 10, 100, 1000):
for i in range(10):
for j in range(10):
num = i * d + j * (d * 10) + i + j
if low <= num <= high and num >= 10:
count += 1
return count
low = 1
high = 100
print(count_symmetric_integers_by_digits(low, high))public class SymmetricIntegerByDigits {
public static int countSymmetricIntegersByDigits(int low, int high) {
int count = 0;
for (int d = 1; d <= 9999; d *= 10) {
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
int num = i * d + j * (d * 10) + i + j;
if (num >= low && num <= high && num >= 10) {
count++;
}
}
}
}
return count;
}
public static void main(String[] args) {
int low = 1, high = 100;
System.out.println(countSymmetricIntegersByDigits(low, high));
}
}#include <iostream>
int count_symmetric_integers_by_digits(int low, int high) {
int count = 0;
for (int d = 1; d <= 9999; d *= 10) {
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
int num = i * d + j * (d * 10) + i + j;
if (num >= low && num <= high && num >= 10) {
count++;
}
}
}
}
return count;
}
int main() {
int low = 1, high = 100;
std::cout << count_symmetric_integers_by_digits(low, high) << std::endl;
return 0;
}function countSymmetricIntegersByDigits(low, high) {
let count = 0;
for (let d = 1; d <= 9999; d *= 10) {
for (let i = 0; i < 10; i++) {
for (let j = 0; j < 10; j++) {
const num = i * d + j * (d * 10) + i + j;
if (num >= low && num <= high && num >= 10) {
count++;
}
}
}
}
return count;
}
console.log(countSymmetricIntegersByDigits(1, 100));#include <stdio.h>
int count_symmetric_integers_by_digits(int low, int high) {
int count = 0;
for (int d = 1; d <= 9999; d *= 10) {
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
int num = i * d + j * (d * 10) + i + j;
if (num >= low && num <= high && num >= 10) {
count++;
}
}
}
}
return count;
}
int main() {
int low = 1, high = 100;
printf("%d\n", count_symmetric_integers_by_digits(low, high));
return 0;
}using System;
public class SymmetricIntegersByDigits {
public static int CountSymmetricIntegersByDigits(int low, int high) {
int count = 0;
for (int d = 1; d <= 9999; d *= 10) {
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
int num = i * d + j * (d * 10) + i + j;
if (num >= low && num <= high && num >= 10) {
count++;
}
}
}
}
return count;
}
public static void Main() {
int low = 1, high = 100;
Console.WriteLine(CountSymmetricIntegersByDigits(low, high));
}
}This Python function uses nested loops over digit values and evaluates possible symmetric numbers by constructing them directly, leveraging mirrored pairs and checking if they fall within the provided range.
Time Complexity: O(D^2), since we iterate through mirrored digit combinations to form numbers.
Space Complexity: O(1), with no additional space for structures beyond simple counters.
Approach 3: Enumeration
We enumerate each integer x in the range [low, high], and check whether it is a palindromic number. If it is, then the answer ans is increased by 1.
The time complexity is O(n times log m), and the space complexity is O(log m). Here, n is the number of integers in the range [low, high], and m is the maximum integer given in the problem.
function countSymmetricIntegers(low: number, high: number): number {
let ans = 0;
const f = (x: number): number => {
const s = x.toString();
const n = s.length;
if (n & 1) {
return 0;
}
let a = 0;
let b = 0;
for (let i = 0; i < n >> 1; ++i) {
a += Number(s[i]);
b += Number(s[(n >> 1) + i]);
}
return a === b ? 1 : 0;
};
for (let x = low; x <= high; ++x) {
ans += f(x);
}
return ans;
}func countSymmetricIntegers(low int, high int) (ans int) {
f := func(x int) int {
s := strconv.Itoa(x)
n := len(s)
if n&1 == 1 {
return 0
}
a, b := 0, 0
for i := 0; i < n/2; i++ {
a += int(s[i] - '0')
b += int(s[n/2+i] - '0')
}
if a == b {
return 1
}
return 0
}
for x := low; x <= high; x++ {
ans += f(x)
}
return
}impl Solution {
pub fn count_symmetric_integers(low: i32, high: i32) -> i32 {
let mut ans = 0;
for x in low..=high {
ans += Self::f(x);
}
ans
}
fn f(x: i32) -> i32 {
let s = x.to_string();
let n = s.len();
if n % 2 == 1 {
return 0;
}
let bytes = s.as_bytes();
let mut a = 0;
let mut b = 0;
for i in 0..n / 2 {
a += (bytes[i] - b'0') as i32;
}
for i in n / 2..n {
b += (bytes[i] - b'0') as i32;
}
if a == b { 1 } else { 0 }
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(N * D), due to checking each number in the range and processing its digits. Space Complexity: O(D), as digits are stored in a string per calculation. |
| Digit Analysis Approach | Time Complexity: O(D^2), since we iterate through mirrored digit combinations to form numbers. Space Complexity: O(1), with no additional space for structures beyond simple counters. |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n * d) | O(1) | Best for clarity and quick implementation when constraints are small |
| Digit Analysis | O(n) | O(1) | Preferred in interviews; avoids string conversion and uses direct digit math |
Frequently asked questions
Is Count Symmetric Integers easy or hard?
Count Symmetric Integers is categorized as an Easy problem. The logic relies on simple digit manipulation and range iteration, making it a good exercise for beginners practicing math-based enumeration problems.
Count Symmetric Integers Python/Java solution
Python and Java implementations both iterate through the range and check digit symmetry. Python often uses string slicing for simplicity, while Java commonly extracts digits with division and modulo. Both versions run in O(n) time and constant space.
How to solve Count Symmetric Integers in O(n)?
Iterate through the range and skip numbers with odd digit counts. For valid numbers, extract digits using arithmetic operations like modulo and division. Compare the sum of the first half of digits with the second half. Each number is processed in constant time, giving O(n) overall complexity.
What is the best approach for Count Symmetric Integers?
Digit analysis is the best approach. Iterate from low to high and check only numbers with an even digit count. Extract digits using division and modulo, then compare the sum of the first half and second half. This runs in O(n) time and O(1) space.
Is Count Symmetric Integers asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving digit manipulation and enumeration. Variants of digit-sum checks and numeric property problems appear in interviews at companies like Amazon and Google to evaluate basic algorithmic reasoning.
What data structure is used in Count Symmetric Integers?
No complex data structures are required. The solution mainly uses integer arithmetic and basic loops. Some implementations convert numbers to strings, but the optimal approach relies on direct digit extraction using math operations.
What is the time complexity of Count Symmetric Integers?
The typical optimized solution runs in O(n) time where n is the size of the range (high - low + 1). Each number is checked with constant-time digit extraction. Space complexity remains O(1) since only a few variables are used.