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:

  1. The input number is a string x of known length (n)
  2. 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.


« 上一篇: 理解线索二叉树