1. Introduction
In this tutorial, we’ll show how to check if a number is balanced.
2. Definition of Balanced Numbers and Problem Settings
We say that a number is balanced if the sum of digits in its left half equals the sum in its right half.
For example, 123213 is balanced because 1+2+3=2+1+3.
We won’t consider the middle digit if the input number has an odd number of digits. So, 123d213 is balanced no matter the value of d.
We’ll consider two formulations of this problem depending on the input x:
- The input number is a string x of known length (n)
- The input is a numeric value for which we don’t know the number of digits.
3. String Input
No matter the parity of n, the left half is x[1:floor(n/2)]. Let’s take a look at two examples:
x = "12345678"
n = 8
floor(n/2) = floor(8/2) = floor(4) = 4
left half = "1234"
right half = "5678"
x = "123456789"
n = 9
floor(9/2) = floor(9/2) = floor(4.5) = 4
left half = "1234"
right half = "6789"
The start position of the right half differs for odd and even strings. If n is even, the right half is x[(floor(n/2)+1): n]. For an odd n, we skip the middle element x[(floor(n/2))+1], so the right half is x[(floor(n/2)+2):n].
Therefore, we traverse the string, add up the numerical values of the digits in the left half, and subtract the values in the right half:
algorithm Balanced(x):
// INPUT
// x = the input string with n digits (1-based indexing)
// OUTPUT
// Returns true if x represents a balanced string, and false otherwise.
s = 0
for i <- 1 to floor(n/2):
s <- s + integer(x[i])
if n mod 2 = 1:
right_start <- floor(n/2) + 2
else:
right_start <- floor(n/2)
for i <- right_start to n:
s <- s - integer(x[i])
if s = 0:
return true
else:
return false
If s is zero in the end, the left and right sums are equal.
Since x is a string in this formulation, its elements x[i] are characters, so we need to convert them to integers.
3.1. Examples with Strings
Let’s check out an example with even n:
x = "12343142"
n = 8
// first loop (over the left half)
s = 1 + 2 + 3 + 4 = 10
// 8 is even, so right_start = floor(8/2)+ 1 = 5
s = 10 - 3 - 1 - 4 - 2 = 0
The algorithm also works for odd-length strings:
x = "123453142"
n = 9
// first loop (over the left half)
s = 1 + 2 + 3 + 4 = 10
// 9 is odd, so right_start = floor(9/2)+ 2 = 6
s = 10 - 3 - 1 - 4 - 2 = 0
3.2. Complexity
The asymptotic notation shows us how the performance of our algorithm depends on the input size as it tends to infinity.
We iterate over the string once, and casting characters to integers is an O(1) operation, so *the time complexity is O(n).* Since we need to store n characters of the input string, *the space complexity is also O(n).*
4. Numeric Input
In this formulation, x is an integer, and we don’t know how many digits it has.
4.1. Precompute the Number of Digits
One approach is to determine the number of digits by repeatedly dividing x by 10 until reaching 0. The number of divisions (n) equals the number of digits, so we can proceed similarly to the string case.
The difference is that now, we start from the end of the right half and iterate over digits from the least to the most significant one:
algorithm Balanced(x):
// INPUT
// x = the input integer
// OUTPUT
// Returns true if x is balanced, and false otherwise.
s = 0
z <- x
n <- 0
while z > 0:
z <- z div 10
n <- n + 1
if n mod 2 = 1:
right_start <- floor(n/2) + 2
else:
right_start <- floor(n/2)
i <- n
while i >= right_start:
s <- s + (x mod 10)
x <- x div 10
i <- i - 1
if n mod 2 = 1:
x <- x div 10
while x >= 0:
s <- s - (x mod 10)
x <- x div 10
if s = 0:
return true
else:
return false
If x contains an odd number of digits, we do an additional integer division before processing the left half to skip the middle digits.
4.2. Complexity
As the input size n tends to infinity, we need more and more bits to store x in RAM. In particular, we need at least log_2(n) + 1 bits, so the space complexity is O(log n), and the mod and div operations don’t have constant but logarithmic complexity. As a result, *the overall time complexity is O(n log n).*
However, in some computational models, such as the word RAM or real RAM, all arithmetic operations are O(1) regardless of the magnitude of their arguments. In such models, this algorithm’s time complexity is O(n), and space complexity is O(1).
5. “Two-Pointers” Approach
Alternatively, we can skip the precomputation of n for the integer input. To do so, we follow the logic of the two-pointers approach and copy x to another variable, z, adding and subtracting the digits of x from the least the most significant one.
The trick is to replace z with z div 100 whenever we replace x with x div 10. Consequently, when z is reduced to a single digit or 0, x will be equal to the left half of the input:
algorithm Balanced(x):
// INPUT
// x = the input integer
// OUTPUT
// Returns true if x is balanced, and false otherwise.
s = 0
z <- x
while z > 9:
s <- x + (x mod 10)
x <- x div 10
z <- z div 100
if z > 0:
x <- x div 10
while x > 0:
s <- s - (x mod 10)
x <- x div 10
if s = 0:
return true
else:
return false
If z = 0 after the first loop, the input had an even number of digits. Otherwise (0 < z <= 9), we skip the middle digit by executing an additional replacement x <- x div 10. Afterward, we process the left half.
The complexity stays the same, but the pseudocode is more succinct.
5.1. Examples
Let’s check out an example with even n:
x z s
12343142 12343142 0
1234314 123431 2
123431 1234 6
12343 12 7
1234 0 10 // break the first loop
123 0 6
12 0 3
1 0 1
0 0 0
The algorithm also works for odd-length strings:
x z s
123453142 123453142 0
12345314 1234531 2
1234531 12345 6
123453 123 7
12345 1 10 // break the first loop
1234 1 10 // additional div 10 for x
123 1 6
12 1 3
1 1 1
0 1 0
6. Conclusion
In this article, we showed how to check if a number is balanced. We covered two cases of input: string and integer.
The algorithm for the string input runs in linear time and has linear space complexity. The algorithm for integer input runs in log-linear time and has logarithmic space complexity unless we assume computational models with constant arithmetic operations.