3340. Check Balanced String

EasyString

Problem Description

You are given a string num consisting of only digits. A string of digits is called balanced if the sum of the digits at even indices is equal to the sum of the digits at odd indices. Return true if num is balanced, otherwise return false.

Intuition

To determine if the string num is balanced, we can maintain two sums: one for the digits at even indices and another for the digits at odd indices. By iterating through the string, we map each character to its integer value and add it to the appropriate sum based on whether its index is even or odd. Once all characters have been processed, we compare the two sums. If they are equal, the string is balanced; otherwise, it is not.

Solution Approach

The solution utilizes a simple simulation approach. The idea is to use an array f with two elements to track the sums of the numbers at even and odd indices separately.

Initialize: Start by initializing an array f with two elements, both set to zero, representing the sums for even and odd indices.
```
f = [0, 0]
```
Iterate through the string num:
- Convert each character in num to an integer.
- For each character, determine its index i.
- Use the bitwise AND operator (&) to check the parity of the index: i & 1 will be 0 if i is even and 1 if i is odd.
- Accumulate the sum for even indices in f[0] and for odd indices in f[1].
```
for i, x in enumerate(map(int, num)):
    f[i & 1] += x
```
Check if the string is balanced:
- Compare the two sums: f[0] and f[1].
- Return True if they are equal, indicating the string is balanced. Otherwise, return False.
```
return f[0] == f[1]
```

This approach ensures that you efficiently traverse the string once, with a time complexity of O(n), where n is the length of the string num. The space complexity is constant O(1) since we only use a fixed-size array regardless of input size.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider the string num = "123123" to illustrate the approach:

Initialize the sum array:
- Start with f = [0, 0], where f[0] will track the sum of digits at even indices, and f[1] will track the sum of digits at odd indices.
Iterate through the string num:
- Index 0 ('1'):
  - Convert '1' to integer 1.
  - Since 0 & 1 = 0, add 1 to f[0].
  - f becomes [1, 0].
- Index 1 ('2'):
  - Convert '2' to integer 2.
  - Since 1 & 1 = 1, add 2 to f[1].
  - f becomes [1, 2].
- Index 2 ('3'):
  - Convert '3' to integer 3.
  - Since 2 & 1 = 0, add 3 to f[0].
  - f becomes [4, 2].
- Index 3 ('1'):
  - Convert '1' to integer 1.
  - Since 3 & 1 = 1, add 1 to f[1].
  - f becomes [4, 3].
- Index 4 ('2'):
  - Convert '2' to integer 2.
  - Since 4 & 1 = 0, add 2 to f[0].
  - f becomes [6, 3].
- Index 5 ('3'):
  - Convert '3' to integer 3.
  - Since 5 & 1 = 1, add 3 to f[1].
  - f becomes [6, 6].
Check if the string is balanced:
- Compare f[0] and f[1]. Here, f[0] = 6 and f[1] = 6.
- Since the sums are equal, return True, indicating that the string num is balanced.

Solution Implementation

1class Solution:
2    def isBalanced(self, num: str) -> bool:
3        # Initialize two counters for sums of digits at even and odd positions
4        sum_even, sum_odd = 0, 0
5      
6        # Iterate over the enumerated digits of 'num' after converting each to an integer
7        for index, digit in enumerate(map(int, num)):
8            # If the index is even, add the digit to sum_even, otherwise add to sum_odd
9            if index % 2 == 0:
10                sum_even += digit
11            else:
12                sum_odd += digit
13      
14        # Check if the sums of digits at even and odd positions are equal
15        return sum_even == sum_odd
16

1class Solution {
2    // This method checks if the sum of digits at even indices equals the sum of digits at odd indices
3    public boolean isBalanced(String num) {
4        int[] sums = new int[2];  // Array to hold sum of digits at even [0] and odd [1] indices
5      
6        // Loop through each character in the string
7        for (int i = 0; i < num.length(); ++i) {
8            int digit = num.charAt(i) - '0';  // Convert character to integer digit
9            sums[i % 2] += digit;  // Add digit to sums, even-indexed go to sums[0], odd-indexed to sums[1]
10        }
11      
12        return sums[0] == sums[1];  // Return true if both sums are equal, otherwise false
13    }
14}
15

1class Solution {
2public:
3    bool isBalanced(std::string num) {
4        int frequency[2] = {0, 0};  // Array to count the sums of digits at even and odd indices.
5
6        // Loop through each character in the string, converting it to an integer digit and updating the sum.
7        for (int i = 0; i < num.size(); ++i) {
8            frequency[i % 2] += num[i] - '0';  // Add the digit to either the even or odd index sum.
9        }
10
11        // Return true if the sums of digits at even and odd indices are the same, false otherwise.
12        return frequency[0] == frequency[1];
13    }
14};
15

1// Function to check if the sum of digits at even indices equals
2// the sum of digits at odd indices in the given string representation of a number.
3function isBalanced(num: string): boolean {
4    // Array to store the sum of digits at even and odd indices.
5    const balanceSum = [0, 0];
6
7    // Loop through each character in the string.
8    for (let i = 0; i < num.length; ++i) {
9        // Convert character to number and add it to the appropriate index in balanceSum
10        // 'i & 1' evaluates to 0 for even 'i' and 1 for odd 'i'.
11        balanceSum[i & 1] += +num[i];
12    }
13
14    // Check if both sums are equal and return the result.
15    return balanceSum[0] === balanceSum[1];
16}
17

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the string num. This is because the algorithm iterates through each character of the string once, performing constant-time operations for each character.

The space complexity is O(1). The algorithm uses a fixed amount of extra space for the list f which consists of two integers, regardless of the input size.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don’t know