Server energy balancing

Solutions

There exist several approaches and solutions to this problem. Some are very intuitive, others require to rack one’s brain. This challenge is a variation of the “Equilibrium Index,” and since it’s available as Sherlock and Array on this website, we won’t revisit all the solutions discussed there. For instance, solutions based on the prefix sum pattern are not covered here but can also be applied to this problem.

For completeness, we mention the brute force solution that consists in iterating through potential server values from 1 to \( n \). For each server \( i \), we calculate the left and right sums using nested loops: the first loop sums elements from server 1 to \( i \), and the second loop sums elements from server \( i \) to \( n \). After computing both sums, we check if they are equal. If so, server \( i \) is the balancing server. If no valid balancing server is found after all iterations, we return \(-1\). This approach has a time complexity of \( O(n^2) \) due to the nested loops.

Linear solution based on the sum of the range

An improvement to the brute-force approach involves first calculating the total sum of numbers from 1 to \( n \). Then, we use a cumulative sum leftSum and iterate through the numbers from 1 to \( n \). For each number, we subtract it from the total sum (representing the “right” sum) and check if leftSum equals the remaining sum. If they are equal, we return the current number as the balancing point. If no balance is found, we return -1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


long long findBalancingServer(long long n)
{
    long long total = 0;
    for (long long i=0; i<=n; ++i)
        total += i;
    
    long long leftSum = 0;
    
    for (auto i=1ll; i<=n; ++i)
    {
        total -= i;
        if (total == leftSum)
        {
            return i;
        }
        leftSum += i;
    }
    return -1;
}

The solution is linear in time and constant in space, but it iterates the input array twice.

It’s important to handle data types carefully: if n is an int, large values of n makes the summation overflow. To prevent this, we use long long.

Applying the Gaussian formula for triangular numbers, the sum of numbers from 1 to n can be calculated in constant time:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


long long findBalancingServer(long long n)
{
    auto total = n*(n+1)/2;
    long long leftSum = 0;
    for (auto i=1ll; i<=n; ++i)
    {
        total -= i;
        if (total == leftSum)
        {
            return i;
        }
        leftSum += i;
    }
    return -1;
}

An equivalent solution in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


def findBalancingServer(n):
    total = n * (n + 1) // 2
    left_sum = 0
    
    for i in range(1, n + 1):
        total -= i
        if total == left_sum:
            return i
        left_sum += i
    
    return -1

However, the solution still operates with linear time complexity.

Linear solution based on “two-pointer” technique

Another single-scan approach consists in comparing sums from both ends of the range, using the two-pointer technique. Actually, pointers here are just numbers within the range \([1, n]\). We use n as the second “pointer”. We start with pointers at both ends (left=1 and n unchanged) and adjusts the sums by moving the pointers toward the center. If the left sum is smaller, we add the left value to the sum and move the left pointer right. If the right sum is smaller or equal, we subtract the right value from the sum and move the right pointer left. We return the balancing server when the sums match, or -1 if no balance is found:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


int findBalancingServer(int n)
{
    auto left = 1;
    auto sum = 0;

    while (left <= n)
    {
        if (sum == 0 && left == n)
        {
            return left;
        }

        if (sum >= 0)
        {
            sum -= n--;
        }
        else
        {
            sum += left++;
        }
    }
    return -1;
}

This algorithm runs in linear time, requires no extra space and does not suffer of overflow problems. For this reason, just int values are used. Variants of this approach are based on the same pattern.

Using math

This problem can be approached mathematically since the sum of the input series is described by a well-defined formula.

Indeed, the sum of numbers from \(1\) to \(𝑛\) is:

\(sum = \frac{n \cdot (n + 1)}{2}\)

The sum of numbers from \( 1 \) to \( x \) is:

\(leftSum = \frac{x \cdot (x + 1)}{2}\)

The sum of numbers from \( x \) to \( n \) is:

\(rightSum = \frac{n \cdot (n + 1)}{2} - \frac{x \cdot (x + 1)}{2} + x\)

To find the balancing server \( x \), we set the left and right sums equal:

\(\frac{x \cdot (x + 1)}{2} = \frac{n \cdot (n + 1)}{2} - \frac{x \cdot (x + 1)}{2} + x\)

Combine terms involving \( \frac{x \cdot (x + 1)}{2} \) on the left-hand side:

\(\frac{x \cdot (x + 1)}{2} + \frac{x \cdot (x + 1)}{2} - x = \frac{n \cdot (n + 1)}{2}\)

Simplify:

\(x \cdot (x + 1) - x = \frac{n \cdot (n + 1)}{2}\)

Factor out \( x \):

\(x \cdot x = \frac{n \cdot (n + 1)}{2}\)

Since \( \frac{n \cdot (n + 1)}{2} \) is the total sum of numbers from \( 1 \) to \( n \), the equation simplifies to:

\(x \cdot x = \text{sum}\)

This shows that \( x \) squared equals the total sum when \( x \) is the balancing point. Here is this idea in code:

1
2
3
4
5


long long findBalancingServer(long long n)
{
    long long sum = n * (n + 1) / 2, x = sqrt(sum);
    return x * x == sum ? x : -1;
}

This solution operates in constant time and space.

Note that if the search for the balancing server is to be performed multiple times, we can run a pre-computation step to calculate all the servers for values ranging from 1 to the size of the domain (e.g., \(500,000\)). After that, each query will take constant time. The overall complexity will be \(O(d)\), where \(d\) is the size of the domain.

Binary search

In the general form, the input array consists of any positive number. Rather, in this variant, the theoretical input array consists of increasing positive numbers.

From the previous solution, we know that \( x \) squared equals the total sum when \( x \) is the balancing server. To efficiently find \( x \), we can use binary search by taking advantage of the input’s monotonicity. We begin with the full range from \(1\) to \(n\) and halve the search space at each iteration. If the midpoint squared is smaller than the expected sum, we move the left pointer up, as the right side is too large. Conversely, if the midpoint squared is greater than the expected, we move the right pointer down, as the left side is too small.

Here is the idea code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


long long findBalancingServer(long long n)
{
    long long l = 1, r = n, sum = n * (n + 1) / 2;
    while (l < r)
    {
        auto m = (l + r) / 2;
        if (m * m < sum)
            l = m + 1;
        else
            r = m;
    }
    return l * l == sum ? l : -1;
}

The binary search efficiently reduces the search space by half with each iteration, resulting in a logarithmic time complexity and requires no extra space.