Alternating Digit Sum - Solution & Explanation
Problem Statement
You are given a positive integer n. Each digit of n has a sign according to the following rules:
- The most significant digit is assigned a positive sign.
- Each other digit has an opposite sign to its adjacent digits.
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
Approach Overview
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.
Approach 1: Iterative Approach
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.
Complexity
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.
Approach 2: Recursive Approach
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.
Complexity
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 3: Simulation
We can directly simulate the process as described in the problem.
We define an initial symbol sign=1. Starting from the most significant digit, we take out one digit x each time, multiply it by sign, add the result to the answer, then negate sign, and continue to process the next digit until all digits are processed.
The time complexity is O(log n), and the space complexity is O(log n). Here, n is the given number.
Approach 4: Default Approach
Try this approach in the editor →Complexity Comparison
| 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. |
| Simulation | — |
| Default Approach | — |
Detailed Complexity Analysis
| 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. |
Video Solution
2544. Alternating Digit Sum | Weekly Contest 329 | LeetCode 2544 • Bro Coders • 1,216 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Alternating Digit Sum easy or hard?
Alternating Digit Sum Python/Java solution
How to solve Alternating Digit Sum in O(n)?
What is the best approach for Alternating Digit Sum?
Is Alternating Digit Sum asked at Google/Amazon/Meta?
What data structure is used in Alternating Digit Sum?
What is the time complexity of Alternating Digit Sum?
Ready to solve this problem?
Practice Alternating Digit Sum with our built-in code editor and test cases.
Practice on FleetCode