Check Balanced String
EasyPrompt
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 digits at odd indices.
Return true if num is balanced, otherwise return false.
Example 1:
Input: num = "1234"
Output: false
Explanation:
- The sum of digits at even indices is
1 + 3 == 4, and the sum of digits at odd indices is2 + 4 == 6. - Since 4 is not equal to 6,
numis not balanced.
Example 2:
Input: num = "24123"
Output: true
Explanation:
- The sum of digits at even indices is
2 + 1 + 3 == 6, and the sum of digits at odd indices is4 + 2 == 6. - Since both are equal the
numis balanced.
Constraints:
2 <= num.length <= 100numconsists of digits only
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves iterating through the string twice. The first loop calculates the sum of digits at even indices, and the second loop calculates the sum of digits at odd indices. Finally, it compares the two sums to determine if the string is balanced.
Algorithm
- Initialize two integer variables,
evenSumandoddSum, to 0. - Create a
forloop that iterates from indexi = 0to the end of the string, incrementingiby 2 in each step. Inside this loop, convert the character at the current even index to an integer and add it toevenSum. - Create a second
forloop that iterates from indexi = 1to the end of the string, incrementingiby 2 in each step. Inside this loop, convert the character at the current odd index to an integer and add it tooddSum. - After both loops complete, compare
evenSumandoddSum. If they are equal, returntrue; otherwise, returnfalse.
Walkthrough
The core idea is to handle the even and odd indices in separate passes for clarity. We initialize two variables, evenSum and oddSum, to zero. The first loop iterates from index 0 with a step of 2. In each step, it reads the character, converts it to its integer equivalent (by subtracting the ASCII value of '0'), and adds it to evenSum. The second loop iterates from index 1 with a step of 2. Similarly, it processes the digits at odd indices and accumulates their sum in oddSum. After both loops complete, we check if evenSum is equal to oddSum. If they are equal, the string is balanced, and the function returns true; otherwise, it returns false.
class Solution { public boolean isBalanced(String num) { int evenSum = 0; for (int i = 0; i < num.length(); i += 2) { evenSum += num.charAt(i) - '0'; } int oddSum = 0; for (int i = 1; i < num.length(); i += 2) { oddSum += num.charAt(i) - '0'; } return evenSum == oddSum; }}Complexity
Time
O(N), where N is the length of the string `num`. We traverse the string twice, once for even indices (~N/2 steps) and once for odd indices (~N/2 steps). The total number of operations is proportional to N.
Space
O(1). We only use a few extra variables (`evenSum`, `oddSum`, and loop counters) regardless of the input string size.
Trade-offs
Pros
The logic is very straightforward and easy to understand.
It clearly separates the calculation for even and odd indices, which can make the code easier to read for beginners.
Cons
It iterates through the string's data twice, which is less efficient than a single-pass solution due to increased loop overhead and potentially worse cache performance.
This approach improves upon the previous one by calculating both the sum of digits at even indices and the sum of digits at odd indices in a single pass through the string.
Algorithm
- Initialize two integer variables,
evenSumandoddSum, to 0. - Loop through the string from index
i = 0tonum.length() - 1. - In each iteration, get the numeric value of the character
num.charAt(i). - Check if the current index
iis even using the modulo operator (i % 2 == 0). - If
iis even, add the digit's value toevenSum. - If
iis odd, add the digit's value tooddSum. - After the loop, return the result of
evenSum == oddSum.
Walkthrough
Instead of two separate loops, we can use a single loop that iterates from the beginning to the end of the string. We still maintain two variables, evenSum and oddSum. Inside the loop, for each index i, we check if it's even or odd. If the index i is even, we add the corresponding digit's value to evenSum. If the index i is odd, we add the digit's value to oddSum. This way, we build both sums simultaneously. After the loop finishes, we compare evenSum and oddSum for equality.
class Solution { public boolean isBalanced(String num) { int evenSum = 0; int oddSum = 0; for (int i = 0; i < num.length(); i++) { int digit = num.charAt(i) - '0'; if (i % 2 == 0) { evenSum += digit; } else { oddSum += digit; } } return evenSum == oddSum; }}Complexity
Time
O(N), where N is the length of the string `num`. We traverse the string only once.
Space
O(1). We use a constant amount of extra space for the sum variables and the loop counter.
Trade-offs
Pros
More efficient than the two-loop approach as it requires only one pass over the data.
The logic remains clear and easy to understand while being more performant.
Cons
Requires a conditional check inside the loop, which is a very minor performance consideration compared to the two-loop approach's overhead.
This is the most optimized approach. It uses a single pass and a single variable to track the difference between the sum of digits at even indices and the sum of digits at odd indices.
Algorithm
- Initialize a single integer variable,
difference, to 0. - Loop through the string from index
i = 0tonum.length() - 1. - In each iteration, get the numeric value of the character
num.charAt(i). - Check if the current index
iis even (i % 2 == 0). - If
iis even, add the digit's value todifference. - If
iis odd, subtract the digit's value fromdifference. - After the loop, return
trueifdifferenceis 0, andfalseotherwise.
Walkthrough
The condition sum_even == sum_odd is equivalent to sum_even - sum_odd == 0. We can compute this difference directly in one pass. Initialize a single variable, difference, to 0. Iterate through the string. For each digit, if it's at an even index, add its value to difference. If it's at an odd index, subtract its value from difference. After iterating through the entire string, if difference is 0, it means the sums were equal, and the string is balanced.
class Solution { public boolean isBalanced(String num) { int difference = 0; for (int i = 0; i < num.length(); i++) { int digit = num.charAt(i) - '0'; if (i % 2 == 0) { difference += digit; } else { difference -= digit; } } return difference == 0; }}Complexity
Time
O(N), where N is the length of the string `num`. The algorithm performs a single pass over the string.
Space
O(1). It uses only one extra variable for the difference and a loop counter, making it the most space-efficient variant.
Trade-offs
Pros
Most efficient in terms of both time (single pass) and space (one accumulator variable).
Leads to concise and compact code.
Cons
The logic of adding and subtracting into a single variable might be slightly less intuitive for a beginner compared to maintaining two separate, explicit sums.
Solutions
Solution
class Solution {public boolean isBalanced(String num) { int[] f = new int[2]; for (int i = 0; i < num.length(); ++i) { f[i & 1] += num.charAt(i) - '0'; } return f[0] == f[1]; }}/** * @param {string} num * @return {boolean} */ var isBalanced = function ( num,) { const f = [0, 0]; for (let i = 0; i < num.length; ++i) { f[i & 1] += +num[i]; } return f[0] === f[1];};public class Solution { public bool IsBalanced(string num) { int[] f = new int[2]; for (int i = 0; i < num.Length; ++i) { f[i & 1] += num[i] - '0'; } return f[0] == f[1]; }}class Solution {public: bool isBalanced(string num) { int f[2]{}; for (int i = 0; i < num.size(); ++i) { f[i & 1] += num[i] - '0'; } return f[0] == f[1]; }};class Solution: def isBalanced(self, num: str) -> bool: f = [0, 0] for i, x in enumerate(map(int, num)): f[i & 1] += x return f[0] == f[1]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.