2544. Alternating Digit Sum - Solution

Q: Is Alternating Digit Sum easy or hard?

Alternating Digit Sum is categorized as an Easy problem. It focuses on digit extraction, iteration, and sign management rather than advanced algorithms or data structures.

Q: Alternating Digit Sum Python/Java solution

In Python or Java, convert the number to a string and iterate through each character. Parse the digit, add it when the index is even, subtract it when the index is odd, and keep updating a running total. This implementation runs in O(d) time with constant auxiliary space.

Q: How to solve Alternating Digit Sum in O(n)?

Treat n as a sequence of digits and iterate through them once. Maintain a running sum and a sign variable that flips between +1 and -1 after each digit. Adding digit * sign during the pass computes the alternating sum in linear time relative to the number of digits.

Q: What is the best approach for Alternating Digit Sum?

The iterative digit processing approach is the most practical solution. Traverse the digits from left to right, add digits at even positions and subtract digits at odd positions. This runs in O(d) time where d is the number of digits and uses O(1) extra space.

Q: Is Alternating Digit Sum asked at Google/Amazon/Meta?

Alternating Digit Sum is an easy-level problem commonly used in coding screens to test basic number manipulation and iteration logic. While not a classic FAANG interview staple, problems with similar digit-processing patterns appear in interviews at companies like Amazon and Google.

Q: What data structure is used in Alternating Digit Sum?

No specialized data structure is required. The problem is solved using simple arithmetic operations or by iterating through a string representation of the number, along with a running accumulator and sign toggle.

Q: What is the time complexity of Alternating Digit Sum?

The time complexity is O(d), where d is the number of digits in the integer. Each digit is processed exactly once while computing the alternating sum, and no additional nested operations are required.

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

Approach overview

Problem Overview: Given an integer n, compute the alternating sum of its digits. The leftmost digit is added, the next digit is subtracted, the next added again, and the pattern continues until the last digit.

Approach 1: Iterative Digit Processing (O(d) time, O(1) space)

This approach walks through the digits and flips the sign after every step. The easiest implementation converts the number to a string and iterates from left to right. Add the digit when the index is even and subtract it when the index is odd. The key insight is that the problem is purely positional; you only need a running sum and a sign toggle.

You can also process digits mathematically using n % 10 and n / 10, but then you must account for the fact that digits are processed from right to left. Converting to a string keeps the implementation simple and avoids parity adjustments. This solution performs a single pass over d digits, giving O(d) time complexity with constant auxiliary space.

The approach is essentially a small math simulation problem: iterate, apply sign, flip sign, repeat.

Approach 2: Recursive Digit Evaluation (O(d) time, O(d) space)

The recursive version models the alternating pattern directly with function calls. Convert the number to a string and define a helper function that processes the digit at index i. Each call contributes either +digit or -digit depending on whether i is even or odd, then recursively evaluates the next index.

The recursion naturally mirrors the alternating structure of the problem: process current digit, flip the sign implicitly via index parity, and move forward. The recursion depth equals the number of digits, so the stack uses O(d) space. Time complexity remains O(d) because each digit is processed once.

This version is mainly educational and highlights how simple numeric problems can map to recursion. In production or interviews, the iterative solution is usually preferred because it avoids call stack overhead.

Recommended for interviews: The iterative approach is the expected solution. It runs in O(d) time with O(1) extra space and clearly shows you understand digit extraction and sign toggling. Mentioning the recursive variant demonstrates deeper understanding of problem decomposition, but the loop-based method is cleaner and more practical.

Approach 1: Iterative Approach

In this approach, we can iterate through each digit of the number, starting from the most significant digit. We alternate the sign of each digit and accumulate the sum, starting with a positive sign for the most significant digit.

Python

def alternating_digit_sum(n):
    num_str = str(n)
    sum = 0
    sign = 1
    for digit in num_str:
        sum += sign * int(digit)
        sign = -sign
    return sum

n = 521
print("Sum:", alternating_digit_sum(n))

Java

public class AlternatingDigitSum {
    public static void main(String[] args) {
        int n = 521;
        System.out.println("Sum: " + alternatingDigitSum(n));
    }

    public static int alternatingDigitSum(int n) {
        String numStr = String.valueOf(n);
        int sum = 0;
        int sign = 1;
        for (int i = 0; i < numStr.length(); i++) {
            sum += sign * (numStr.charAt(i) - '0');
            sign = -sign;
        }
        return sum;
    }
}

C++

#include <iostream>
#include <string>

int alternatingDigitSum(int n) {
    std::string num = std::to_string(n);
    int sum = 0;
    int sign = 1;
    for (char digit : num) {
        sum += sign * (digit - '0');
        sign = -sign;
    }
    return sum;
}

int main() {
    int n = 521;
    std::cout << "Sum: " << alternatingDigitSum(n) << std::endl;
    return 0;
}

JavaScript

function alternatingDigitSum(n) {
    let numStr = n.toString();
    let sum = 0;
    let sign = 1;
    for (let char of numStr) {
        sum += sign * parseInt(char);
        sign = -sign;
    }
    return sum;
}

let n = 521;
console.log('Sum:', alternatingDigitSum(n));

#include <stdio.h>
#include <stdlib.h>

int alternatingDigitSum(int n) {
    int sign = 1; // Start with positive sign
    int sum = 0;
    while (n > 0) {
        // Extract the last digit
        int digit = n % 10;
        // Add digit with appropriate sign
        sum += sign * digit;
        // Reverse sign for the next digit
        sign = -sign;
        // Remove the last digit
        n /= 10;
    }
    return sum;
}

int main() {
    int n = 521;
    printf("Sum: %d", alternatingDigitSum(n));
    return 0;
}

using System;

class Program {
    static void Main() {
        int n = 521;
        Console.WriteLine("Sum: " + AlternatingDigitSum(n));
    }

    static int AlternatingDigitSum(int n) {
        string numStr = n.ToString();
        int sum = 0;
        int sign = 1;
        foreach (char digit in numStr) {
            sum += sign * (digit - '0');
            sign = -sign;
        }
        return sum;
    }
}

This Python solution follows the same pattern: convert to string, iterate, switch signs, and accumulate the sum. Each digit is extracted by iterating through the string representation of the digit, simplifying development.

Complexity

Time Complexity: O(d), where d is the number of digits in n.
Space Complexity: O(1), additional space usage is minimal and independent of input size.

Try this approach in the editor

Approach 2: Recursive Approach

This approach relies on recursion to process each digit of the number, alternating the sign with each recursive call while reducing the complete integer by moving one digit to the right at each call.

Python

def alternating_digit_sum(n, sign=1):
    if n == 0:
        return 0
    digit = n % 10
    return sign * digit + alternating_digit_sum(n // 10, -sign)

n = 521
print('Sum:', alternating_digit_sum(n))

Java

public class AlternatingDigitSum {
    public static void main(String[] args) {
        int n = 521;
        System.out.println("Sum: " + alternatingDigitSum(n));
    }

    public static int alternatingDigitSum(int n) {
        return recursiveSum(n, 1);
    }

    private static int recursiveSum(int n, int sign) {
        if (n == 0) return 0;
        int digit = n % 10;
        return sign * digit + recursiveSum(n / 10, -sign);
    }
}

C++

#include <iostream>

int recursiveSum(int n, int sign) {
    if (n == 0)
        return 0;
    int digit = n % 10;
    return sign * digit + recursiveSum(n / 10, -sign);
}

int alternatingDigitSum(int n) {
    return recursiveSum(n, 1);
}

int main() {
    int n = 521;
    std::cout << "Sum: " << alternatingDigitSum(n) << std::endl;
    return 0;
}

JavaScript

function alternatingDigitSum(n, sign = 1) {
    if (n === 0) return 0;
    let digit = n % 10;
    return sign * digit + alternatingDigitSum(Math.floor(n / 10), -sign);
}

let n = 521;
console.log('Sum:', alternatingDigitSum(n));

#include <stdio.h>

int recursiveSum(int n, int sign) {
    if (n == 0)
        return 0;
    int digit = n % 10;
    return sign * digit + recursiveSum(n / 10, -sign);
}

int alternatingDigitSum(int n) {
    return recursiveSum(n, 1);
}

int main() {
    int n = 521;
    printf("Sum: %d", alternatingDigitSum(n));
    return 0;
}

using System;

class Program {
    static void Main() {
        int n = 521;
        Console.WriteLine("Sum: " + AlternatingDigitSum(n));
    }

    static int AlternatingDigitSum(int n) {
        return RecursiveSum(n, 1);
    }

    static int RecursiveSum(int n, int sign) {
        if (n == 0) return 0;
        int digit = n % 10;
        return sign * digit + RecursiveSum(n / 10, -sign);
    }
}

The recursive Python version utilizes an optional argument to toggle signs, permitting a natural, simplified call structure devoid of explicit helper functions, directly traversing through each digit recursively.

Complexity

Time Complexity: O(d), stemming from the complete traversal across all digits via recursive calls.
Space Complexity: O(d), corresponding to the recursive stack depth as the function progresses.

Try this approach in the editor

Approach 3: Simulation

We can directly simulate the process as described in the problem.

We define an initial symbol sign=1. Starting from the most significant digit, we take out one digit x each time, multiply it by sign, add the result to the answer, then negate sign, and continue to process the next digit until all digits are processed.

The time complexity is O(log n), and the space complexity is O(log n). Here, n is the given number.

TypeScript

function alternateDigitSum(n: number): number {
    let ans = 0;
    let sign = 1;
    while (n) {
        ans += (n % 10) * sign;
        sign = -sign;
        n = Math.floor(n / 10);
    }
    return ans * -sign;
}

func alternateDigitSum(n int) (ans int) {
	sign := 1
	for _, c := range strconv.Itoa(n) {
		x := int(c - '0')
		ans += sign * x
		sign *= -1
	}
	return
}

Rust

impl Solution {
    pub fn alternate_digit_sum(mut n: i32) -> i32 {
        let mut ans = 0;
        let mut sign = 1;
        while n != 0 {
            ans += (n % 10) * sign;
            sign = -sign;
            n /= 10;
        }
        ans * -sign
    }
}

Try this approach in the editor

Approach 4: Default Approach

Rust

impl Solution {
    pub fn alternate_digit_sum(n: i32) -> i32 {
        let mut ans = 0;
        let mut sign = 1;

        for c in format!("{}", n).chars() {
            let x = c.to_digit(10).unwrap() as i32;
            ans += x * sign;
            sign *= -1;
        }

        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Iterative Approach	Time Complexity: O(d), where d is the number of digits in n. Space Complexity: O(1), additional space usage is minimal and independent of input size.
Recursive Approach	Time Complexity: O(d), stemming from the complete traversal across all digits via recursive calls. Space Complexity: O(d), corresponding to the recursive stack depth as the function progresses.
Simulation	–
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Iterative Digit Processing	O(d)	O(1)	Best general solution. Simple loop with sign toggling and minimal memory usage.
Recursive Digit Evaluation	O(d)	O(d)	Useful for demonstrating recursion concepts or when modeling position-based digit processing.

Frequently asked questions

Is Alternating Digit Sum easy or hard?

Alternating Digit Sum is categorized as an Easy problem. It focuses on digit extraction, iteration, and sign management rather than advanced algorithms or data structures.

Alternating Digit Sum Python/Java solution

In Python or Java, convert the number to a string and iterate through each character. Parse the digit, add it when the index is even, subtract it when the index is odd, and keep updating a running total. This implementation runs in O(d) time with constant auxiliary space.

How to solve Alternating Digit Sum in O(n)?

Treat n as a sequence of digits and iterate through them once. Maintain a running sum and a sign variable that flips between +1 and -1 after each digit. Adding digit * sign during the pass computes the alternating sum in linear time relative to the number of digits.

What is the best approach for Alternating Digit Sum?

The iterative digit processing approach is the most practical solution. Traverse the digits from left to right, add digits at even positions and subtract digits at odd positions. This runs in O(d) time where d is the number of digits and uses O(1) extra space.

Is Alternating Digit Sum asked at Google/Amazon/Meta?

Alternating Digit Sum is an easy-level problem commonly used in coding screens to test basic number manipulation and iteration logic. While not a classic FAANG interview staple, problems with similar digit-processing patterns appear in interviews at companies like Amazon and Google.

What data structure is used in Alternating Digit Sum?

No specialized data structure is required. The problem is solved using simple arithmetic operations or by iterating through a string representation of the number, along with a running accumulator and sign toggle.

What is the time complexity of Alternating Digit Sum?

The time complexity is O(d), where d is the number of digits in the integer. Each digit is processed exactly once while computing the alternating sum, and no additional nested operations are required.

Alternating Digit Sum solution and explanation

The problem

Approach overview

Approach 1: Iterative Approach

Approach 2: Recursive Approach

Approach 3: Simulation

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Alternating Digit Sum solution and explanation

The problem

Approach overview

Approach 1: Iterative Approach

Approach 2: Recursive Approach

Approach 3: Simulation

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems