Teaching Kids Programming – Algorithms to Compute the Alternating Digit Sum | ninjasquad

**Teaching Kids Programming**: Videos on **Data Structures and Algorithms**

https://www.youtube.com/watch?v=EciOKlZ-hxw

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^9Hints:

The first step is to loop over the digits. We can convert the integer into a string, an array of digits, or just loop over its digits.

Keep a variable sign that initially equals 1 and a variable answer that initially equals 0.

Each time you loop over a digit i, add sign * i to answer, then multiply sign by -1

### Compute the Alternating Digit Sum From Left to Right

We can convert to string (from the left to the right aka from the Most Significant Digit MSD), and thus it is just doing the math – do what exactly what is being told. Converting to string requires O(N) space, where N is the number of digits. Also, by iterating over the digits, we need to convert characters to integer. The time complexity is O(N) as well.

1 2 3 4 5 6 7 8 9 |
class Solution: def alternateDigitSum(self, n: int) -> int: ans = 0 s = str(n) sign = 1 for i in s: ans += int(i) * sign sign = -sign return ans |

class Solution: def alternateDigitSum(self, n: int) -> int: ans = 0 s = str(n) sign = 1 for i in s: ans += int(i) * sign sign = -sign return ans

### Compute the Alternating Digit Sum From Right to Left

Another way is to do it from right to left, where we can use math % operator to extract the Least Significant Digit (LSD). We can start the sign with minus, flip it along the way to the left, and fix the sign at the end.

1 2 3 4 5 6 7 8 9 |
class Solution: def alternateDigitSum(self, n: int) -> int: ans = 0 sign = 1 while n > 0: sign = - sign ans += sign * (n % 10) n //= 10 return sign * ans |

class Solution: def alternateDigitSum(self, n: int) -> int: ans = 0 sign = 1 while n > 0: sign = - sign ans += sign * (n % 10) n //= 10 return sign * ans

For example, 12, -2+1, and the sign is plus at the end, thus the answer is -1*1=-1, which is correct.

And 123, -3+2-1=-2, the sign is minus at the end, so the answer is -2*-1=2, which is correct: 1-2+3=2.

The time complexity is O(N) where N is the number of digits in the decimal format. The space complexity is O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —

**GD Star Rating***loading…*

609 words

**Last Post**: The C Function to Iterate Over a PyList (PyObject) and Print Each Item (Python C API: PyObject_GetIter)

Source: Internet