# Alternating Digit Sum
**Difficulty:** EASY
[External](https://leetcode.com/problems/alternating-digit-sum)
Canonical: https://scaleengineer.com/dsa/problems/alternating-digit-sum
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [eBay](https://scaleengineer.com/companies/ebay)
---
## Problem
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`

# Approaches
## String Conversion and Iteration
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.
**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`.
**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.
### Explanation
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.

```java
class Solution {
    public int alternateDigitSum(int n) {
        String s = Integer.toString(n);
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            int digit = s.charAt(i) - '0';
            if (i % 2 == 0) {
                sum += digit;
            } else {
                sum -= digit;
            }
        }
        return sum;
    }
}
```
### Algorithm
1. Convert the input integer `n` to its string representation, let's call it `s`.
2. Initialize a variable `sum` to 0.
3. Loop through the string `s` from the first character (index 0) to the last.
4. 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`.
5. After the loop completes, `sum` will hold the final alternating digit sum, which is then returned.

## Mathematical Approach with a Single Pass
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int alternateDigitSum(int n) {
        int sum = 0;
        int sign = 1;
        while (n > 0) {
            int digit = n % 10;
            sum += sign * digit;
            sign *= -1;
            n /= 10;
        }
        // After the loop, 'sign' is 1 if D is even, -1 if D is odd.
        // The correction factor is -sign.
        return sum * -sign;
    }
}
```
### Algorithm
1. Initialize `sum = 0` and `sign = 1`.
2. Loop while `n > 0`.
3. In each iteration, extract the last digit: `digit = n % 10`.
4. Add the signed digit to the sum: `sum += sign * digit`.
5. Flip the sign for the next iteration: `sign *= -1`.
6. Remove the last digit from the number: `n /= 10`.
7. 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`.
8. Return `sum * -sign`.

# Solutions
### Java

```java
class Solution {
public
  int alternateDigitSum(int n) {
    int ans = 0, sign = 1;
    for (char c : String.valueOf(n).toCharArray()) {
      int x = c - '0';
      ans += sign * x;
      sign *= -1;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int alternateDigitSum(int n) {
    int ans = 0, sign = 1;
    for (char c : to_string(n)) {
      int x = c - '0';
      ans += sign * x;
      sign *= -1;
    }
    return ans;
  }
};

```

### Python

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

```