You are given a positive integer n. Each digit of n has a sign according to the following rules:
Return the sum of all digits with their corresponding sign.
Example 1:
Input: n = 521 Output: 4 Explanation: (+5) + (-2) + (+1) = 4.
Example 2:
Input: n = 111 Output: 1 Explanation: (+1) + (-1) + (+1) = 1.
Example 3:
Input: n = 886996 Output: 0 Explanation: (+8) + (-8) + (+6) + (-9) + (+9) + (-6) = 0.
Constraints:
1 <= n <= 109
Problem Overview: Given an integer n, compute the alternating sum of its digits. The leftmost digit is added, the next digit is subtracted, the next added again, and the pattern continues until the last digit.
Approach 1: Iterative Digit Processing (O(d) time, O(1) space)
This approach walks through the digits and flips the sign after every step. The easiest implementation converts the number to a string and iterates from left to right. Add the digit when the index is even and subtract it when the index is odd. The key insight is that the problem is purely positional; you only need a running sum and a sign toggle.
You can also process digits mathematically using n % 10 and n / 10, but then you must account for the fact that digits are processed from right to left. Converting to a string keeps the implementation simple and avoids parity adjustments. This solution performs a single pass over d digits, giving O(d) time complexity with constant auxiliary space.
The approach is essentially a small math simulation problem: iterate, apply sign, flip sign, repeat.
Approach 2: Recursive Digit Evaluation (O(d) time, O(d) space)
The recursive version models the alternating pattern directly with function calls. Convert the number to a string and define a helper function that processes the digit at index i. Each call contributes either +digit or -digit depending on whether i is even or odd, then recursively evaluates the next index.
The recursion naturally mirrors the alternating structure of the problem: process current digit, flip the sign implicitly via index parity, and move forward. The recursion depth equals the number of digits, so the stack uses O(d) space. Time complexity remains O(d) because each digit is processed once.
This version is mainly educational and highlights how simple numeric problems can map to recursion. In production or interviews, the iterative solution is usually preferred because it avoids call stack overhead.
Recommended for interviews: The iterative approach is the expected solution. It runs in O(d) time with O(1) extra space and clearly shows you understand digit extraction and sign toggling. Mentioning the recursive variant demonstrates deeper understanding of problem decomposition, but the loop-based method is cleaner and more practical.
In this approach, we can iterate through each digit of the number, starting from the most significant digit. We alternate the sign of each digit and accumulate the sum, starting with a positive sign for the most significant digit.
The function uses a loop to process each digit from the least significant to the most significant. The sign variable alternates its value between 1 and -1 as we sum up each digit, resulting in the desired alternating sign pattern. The number is reduced by one digit from the right in each iteration using division by 10.
Time Complexity: O(d), where d is the number of digits in n.
Space Complexity: O(1), no extra space used other than variables for sum and sign.
This approach relies on recursion to process each digit of the number, alternating the sign with each recursive call while reducing the complete integer by moving one digit to the right at each call.
The recursive approach defines a helper function that keeps calling itself while reducing the number by a digit. The sign toggles between calls to ensure alternating addition or subtraction.
Time Complexity: O(d), where d is the depth of recursion relative to digit count.
Space Complexity: O(d), used for the call stack as recursion depth equals the number of digits.
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(d), where d is the number of digits in n. |
| Recursive Approach | Time Complexity: O(d), where d is the depth of recursion relative to digit count. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Digit Processing | O(d) | O(1) | Best general solution. Simple loop with sign toggling and minimal memory usage. |
| Recursive Digit Evaluation | O(d) | O(d) | Useful for demonstrating recursion concepts or when modeling position-based digit processing. |
LeetCode#2544 Alternating Digit Sum - Python • CodeJulian • 1,593 views views
Watch 9 more video solutions →Practice Alternating Digit Sum with our built-in code editor and test cases.
Practice on FleetCode