Alternating Digit Sum

Easy

#2324Time: O(D), where D is the number of digits in `n`. Since D is approximately `log10(n)`, the complexity is `O(log n)`. Converting to a string and iterating through it both take time proportional to the number of digits.Space: O(D) or O(log n), where D is the number of digits in n. This is due to the space required to store the string representation of `n`.1 company

Patterns

Math

Companies

eBay

Prompt

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 <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach converts the integer n into its string representation. This allows for easy, left-to-right traversal of the digits. We iterate through the string, and for each digit, we determine its sign based on its position (index). The first digit (at index 0) is positive, the second (at index 1) is negative, and so on.

Algorithm

Convert the input integer n to its string representation, let's call it s.
Initialize a variable sum to 0.
Loop through the string s from the first character (index 0) to the last.
Inside the loop, for each character at index i:
- Convert the character back to its integer value.
- If i is even, the digit has a positive sign. Add its value to sum.
- If i is odd, the digit has a negative sign. Subtract its value from sum.
After the loop completes, sum will hold the final alternating digit sum, which is then returned.

Walkthrough

The algorithm starts by converting the input integer n to a string. This is a very direct way to access the digits from left to right (from most significant to least significant), which matches the problem's definition of how signs are assigned. Once we have the string, we can iterate through it using a standard loop. A simple check on the loop index's parity (even or odd) tells us whether to add or subtract the current digit's value from our running total. For example, at index 0 (the first digit), we add. At index 1 (the second digit), we subtract, and so on. This continues until all digits have been processed.

1class Solution {2    public int alternateDigitSum(int n) {3        String s = Integer.toString(n);4        int sum = 0;5        for (int i = 0; i < s.length(); i++) {6            int digit = s.charAt(i) - '0';7            if (i % 2 == 0) {8                sum += digit;9            } else {10                sum -= digit;11            }12        }13        return sum;14    }15}

Complexity

Time

O(D), where D is the number of digits in `n`. Since D is approximately `log10(n)`, the complexity is `O(log n)`. Converting to a string and iterating through it both take time proportional to the number of digits.

Space

O(D) or O(log n), where D is the number of digits in n. This is due to the space required to store the string representation of `n`.

Trade-offs

Pros

Simple and intuitive to implement.
Directly follows the problem description of processing from the most significant digit.

Cons

Uses extra space proportional to the number of digits, which is less efficient than a purely mathematical approach.

This is a more optimized approach that avoids the overhead of string conversion. It processes the digits mathematically from right to left using the modulo (%) and division (/) operators. Since the sign of a digit depends on its position from the left, and we are processing from the right, a final adjustment to the sum is needed based on the total number of digits.

Algorithm

Initialize sum = 0 and sign = 1.
Loop while n > 0.
In each iteration, extract the last digit: digit = n % 10.
Add the signed digit to the sum: sum += sign * digit.
Flip the sign for the next iteration: sign *= -1.
Remove the last digit from the number: n /= 10.
After the loop, the calculated sum has the correct magnitudes but the signs are relative to the rightmost digit being positive. The final sign variable will be 1 if the number of digits was even, and -1 if it was odd. The necessary correction is to multiply the sum by -sign.
Return sum * -sign.

Walkthrough

This method cleverly calculates the sum in a single pass without needing to know the number of digits beforehand. We iterate from right to left, extracting the last digit with n % 10. We maintain a sign variable, which starts at 1 and flips between 1 and -1 in each iteration. This calculates an alternating sum assuming the rightmost digit is positive.

The key insight is how to adjust this sum to match the problem's requirement (leftmost digit is positive). Let's say the number of digits is D. Our loop calculates d_1 - d_2 + d_3 - ..., where d_1 is the rightmost digit. The correct sum is d_D - d_{D-1} + .... It turns out that if D is odd, our calculated sum is correct. If D is even, our sum is the exact negative of the correct sum. We can determine if D is even or odd by inspecting the final value of our sign variable after the loop. A simple multiplication at the end (sum * -sign) corrects the sum for both cases.

1class Solution {2    public int alternateDigitSum(int n) {3        int sum = 0;4        int sign = 1;5        while (n > 0) {6            int digit = n % 10;7            sum += sign * digit;8            sign *= -1;9            n /= 10;10        }11        // After the loop, 'sign' is 1 if D is even, -1 if D is odd.12        // The correction factor is -sign.13        return sum * -sign;14    }15}

Complexity

Time

O(D), where D is the number of digits in `n`. This is equivalent to `O(log n)`. The algorithm performs a single pass over the digits.

Space

O(1). The algorithm uses only a few variables (`sum`, `sign`, `digit`), requiring constant extra space regardless of the input size.

Trade-offs

Pros

Highly efficient in terms of space (O(1)).
Avoids the overhead of string conversions or creating other data structures.
Achieves the result in a single pass through the digits.

Cons

The logic for the final sign correction (* -sign) is less intuitive than the straightforward string-based approach.

Solutions

Solution

1class Solution {2public3  int alternateDigitSum(int n) {4    int ans = 0, sign = 1;5    for (char c : String.valueOf(n).toCharArray()) {6      int x = c - '0';7      ans += sign * x;8      sign *= -1;9    }10    return ans;11  }12}

1class Solution {2public:3  int alternateDigitSum(int n) {4    int ans = 0, sign = 1;5    for (char c : to_string(n)) {6      int x = c - '0';7      ans += sign * x;8      sign *= -1;9    }10    return ans;11  }12};

1class Solution:2    def alternateDigitSum(self, n: int) -> int: return sum((- 1)3                                                           ** i * int(x) for i, x in enumerate(str(n)))

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.

← Previous

Previous problem

Next problem