Teaching Kids Programming – Algorithms to Compute the Alternating Digit Sum


Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Hints:
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...
572 words
Last Post: The C Function to Iterate Over a PyList (PyObject) and Print Each Item (Python C API: PyObject_GetIter)
Next Post: High-Frequency Trading (HFT) - Triangular Arbitrage Algorithm

The Permanent URL is: Teaching Kids Programming – Algorithms to Compute the Alternating Digit Sum

Leave a Reply