algoadvance

Given a positive integer n, return the alternating sum of its digits starting from the leftmost digit. The alternating sum of a number is defined as:

Example

  1. Input: n = 521 Output: 5 - 2 + 1 = 4
  2. Input: n = 111 Output: 1 - 1 + 1 = 1

Clarifying Questions

  1. Range of n:
    • What is the range of the integer n? (Assuming it is a positive integer and fits within standard integer limits.)
  2. Edge cases:
    • How should the algorithm handle single-digit numbers or numbers with leading zeros?

For the sake of simplicity, let’s assume n is a positive integer with no leading zeros.

Strategy

  1. Convert the Integer to String:
    • Convert the integer n to its string representation to easily access each digit.
  2. Initialize the Sum:
    • Initialize a variable to keep track of the sum (alternating_sum = 0).
  3. Iterate Over Digits:
    • Loop through each digit, convert it back to an integer, and apply the alternating sum logic:
      • For even indexed digits (0-based), add the digit.
      • For odd indexed digits, subtract the digit.
  4. Return the Result:
    • After processing all digits, return the value of alternating_sum.

Code

def alternatingDigitSum(n: int) -> int:
    n_str = str(n)
    alternating_sum = 0
    
    # Iterate over the digits and apply the alternating sum logic
    for idx, digit in enumerate(n_str):
        digit = int(digit)
        if idx % 2 == 0:
            alternating_sum += digit
        else:
            alternating_sum -= digit
    
    return alternating_sum

# Example usage
print(alternatingDigitSum(521))  # Output: 4
print(alternatingDigitSum(111))  # Output: 1

Time Complexity

The time complexity of this algorithm is O(d), where d is the number of digits in the integer n. This is because we are iterating over each digit exactly once. The conversion from integer to string and integer parsing operations inside the loop are all O(1) operations for each digit.

Space Complexity

The space complexity is O(1), as we are using a constant amount of space irrespective of the input size. The string representation of n and the integer sum variable don’t scale with input size in a way that affects asymptotic complexity.

Try our interview co-pilot at AlgoAdvance.com