Problem Description

You are given a string num that contains only digit characters (0-9).

A string of digits is considered balanced when the sum of all digits at even positions (indices 0, 2, 4, ...) equals the sum of all digits at odd positions (indices 1, 3, 5, ...).

Your task is to determine if the given string num is balanced. Return true if it is balanced, and false otherwise.

For example:

• If num = "1234", the digits at even indices are '1' and '3' (sum = 1 + 3 = 4), and the digits at odd indices are '2' and '4' (sum = 2 + 4 = 6). Since 4 ≠ 6, this string is not balanced.
• If num = "24123", the digits at even indices are '2', '1', and '3' (sum = 2 + 1 + 3 = 6), and the digits at odd indices are '4' and '2' (sum = 4 + 2 = 6). Since both sums equal 6, this string is balanced.

The solution uses an array f with two elements to track the sums: f[0] accumulates the sum of digits at even indices, and f[1] accumulates the sum of digits at odd indices. It iterates through each character in the string, converts it to an integer, and adds it to the appropriate sum based on whether the index is even or odd (using i & 1 to determine parity). Finally, it checks if both sums are equal.

Intuition

The problem asks us to compare two groups of digits based on their positions in the string. The natural approach is to separate the digits into two categories: those at even indices and those at odd indices.

Since we need to check if the sums are equal, we need to:

1. Calculate the sum of digits at even positions
2. Calculate the sum of digits at odd positions
3. Compare these two sums

The key insight is that we can do this in a single pass through the string. As we iterate through each character, we can determine whether its index is even or odd and add its value to the appropriate running sum.

To track these two sums efficiently, we can use an array with just two elements: one for even indices and one for odd indices. The expression i & 1 is a clever way to determine if an index is odd or even - it returns 0 for even indices and 1 for odd indices. This is because the bitwise AND operation with 1 effectively checks the least significant bit, which determines parity.

By using f[i & 1] += x, we automatically add each digit to the correct sum based on its position. After processing all digits, we simply need to check if f[0] (sum of even-indexed digits) equals f[1] (sum of odd-indexed digits).

This approach is optimal because it requires only one pass through the string with O(n) time complexity and uses constant extra space O(1) with just the array of size 2.

Solution Approach

The solution uses a simulation approach with an array to track the sums of digits at even and odd indices.

Data Structure Used:

• An array f of length 2 where:
  • f[0] stores the sum of digits at even indices
  • f[1] stores the sum of digits at odd indices

Implementation Steps:

1. Initialize the tracking array: Create f = [0, 0] to store our two sums.

2. Iterate through the string: Use enumerate(map(int, num)) to:

   • Get both the index i and the numeric value x of each character
   • The map(int, num) converts each character to its integer value

3. Accumulate sums based on index parity: For each digit at position i:

   • Calculate i & 1 to determine if the index is even or odd
     • If i is even (0, 2, 4, ...), then i & 1 = 0
     • If i is odd (1, 3, 5, ...), then i & 1 = 1
   • Add the digit value to the appropriate sum: f[i & 1] += x

4. Check balance condition: Return f[0] == f[1] to determine if the string is balanced.

Example walkthrough with num = "24123":

• i=0: digit='2', 0 & 1 = 0, so f[0] += 2 → f = [2, 0]
• i=1: digit='4', 1 & 1 = 1, so f[1] += 4 → f = [2, 4]
• i=2: digit='1', 2 & 1 = 0, so f[0] += 1 → f = [3, 4]
• i=3: digit='2', 3 & 1 = 1, so f[1] += 2 → f = [3, 6]
• i=4: digit='3', 4 & 1 = 0, so f[0] += 3 → f = [6, 6]
• Return 6 == 6 → true

The bitwise AND operation i & 1 is an efficient way to check parity, making this solution both elegant and performant with O(n) time complexity and O(1) space complexity.

Example Walkthrough

Let's walk through the solution with num = "1234":

Initial Setup:

• Initialize array f = [0, 0] where f[0] will track sum of even-indexed digits and f[1] will track sum of odd-indexed digits

Step-by-step Processing:

1. Index 0, digit '1':

   • Convert '1' to integer: x = 1
   • Calculate index parity: 0 & 1 = 0 (even index)
   • Add to even sum: f[0] += 1
   • Array state: f = [1, 0]

2. Index 1, digit '2':

   • Convert '2' to integer: x = 2
   • Calculate index parity: 1 & 1 = 1 (odd index)
   • Add to odd sum: f[1] += 2
   • Array state: f = [1, 2]

3. Index 2, digit '3':

   • Convert '3' to integer: x = 3
   • Calculate index parity: 2 & 1 = 0 (even index)
   • Add to even sum: f[0] += 3
   • Array state: f = [4, 2]

4. Index 3, digit '4':

   • Convert '4' to integer: x = 4
   • Calculate index parity: 3 & 1 = 1 (odd index)
   • Add to odd sum: f[1] += 4
   • Array state: f = [4, 6]

Final Check:

• Compare sums: f[0] == f[1] → 4 == 6 → false
• The string "1234" is not balanced because the sum of digits at even indices (1+3=4) does not equal the sum at odd indices (2+4=6)

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string num. The algorithm iterates through each character in the string exactly once using the enumerate function combined with map(int, num). Each iteration performs constant-time operations: converting a character to an integer, checking the parity of the index with i & 1, and adding to the corresponding sum in the array f.

The space complexity is O(1). The algorithm uses a fixed-size array f with only 2 elements to store the sums of digits at even and odd indices. The space used does not grow with the input size, as we only maintain these two running sums regardless of how long the input string is. The enumerate and map functions create iterators that don't store all values in memory at once, maintaining constant space usage.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing Index Position with Digit Position

A frequent mistake is misunderstanding what "even positions" and "odd positions" mean. Developers might incorrectly interpret this as checking if the digit value itself is even or odd, rather than the index position.

Incorrect approach:

def isBalanced(self, num: str) -> bool:
    even_sum = sum(int(d) for d in num if int(d) % 2 == 0)  # Wrong! Checking digit parity
    odd_sum = sum(int(d) for d in num if int(d) % 2 == 1)   # Wrong! Checking digit parity
    return even_sum == odd_sum

Correct approach:

def isBalanced(self, num: str) -> bool:
    even_sum = sum(int(num[i]) for i in range(0, len(num), 2))  # Indices 0, 2, 4, ...
    odd_sum = sum(int(num[i]) for i in range(1, len(num), 2))   # Indices 1, 3, 5, ...
    return even_sum == odd_sum

2. Off-by-One Error with 1-Based Indexing

Some developers might think in terms of 1-based indexing (positions 1, 2, 3...) instead of 0-based indexing (indices 0, 1, 2...), leading to reversed logic.

Incorrect mental model:

• Position 1 (index 0) → odd position
• Position 2 (index 1) → even position

Correct mental model:

• Index 0 → even position
• Index 1 → odd position

3. Inefficient String-to-Integer Conversion

Converting the character to integer multiple times or using inefficient methods:

Less efficient:

def isBalanced(self, num: str) -> bool:
    sums = [0, 0]
    for i in range(len(num)):
        sums[i & 1] += ord(num[i]) - ord('0')  # Unnecessary complexity
    return sums[0] == sums[1]

Better approach:

def isBalanced(self, num: str) -> bool:
    sums = [0, 0]
    for i, digit in enumerate(num):
        sums[i & 1] += int(digit)  # Direct conversion
    return sums[0] == sums[1]

4. Misunderstanding the Bitwise AND Operation

Not understanding how i & 1 works for determining parity might lead to using less efficient alternatives:

Less optimal alternatives:

# Using modulo (slightly less efficient)
sums[i % 2] += int(digit)

# Using conditional (more verbose)
if i % 2 == 0:
    sums[0] += int(digit)
else:
    sums[1] += int(digit)

While these work correctly, the bitwise AND (i & 1) is the most efficient method for checking if a number is even or odd.