algoadvance

Leetcode 2544. Alternating Digit Sum

Problem Statement

You are given a positive integer n. Each digit of n has a sign according to its position:

• The most significant digit is positive.
• The next digit is negative.
• The next digit is positive, and so on.

Return the sum of all digits of n with their respective signs.

Example:

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

2. Input: n = 111 Output: 1 - 1 + 1 = 1

Clarifying Questions

1. Should we always start with the most significant digit as positive?
   • Yes, the pattern alternates starting with a positive sign for the most significant digit.
2. Should we consider only non-negative integers for n?
   • Yes, we are given that n is a positive integer.
3. What’s the range of the integer n?
   • We assume that n fits within the standard 32-bit integer range (1 to (2^{31}-1)).

Strategy

1. Convert the integer n to a string to easily access each digit by its position.
2. Iterate through the digits and apply the alternating sign based on the position (index) to sum them up correctly.
3. Return the computed sum.

Code

#include <iostream>
#include <string>
using namespace std;

int alternatingDigitSum(int n) {
    string numStr = to_string(n);
    int length = numStr.length();
    int sum = 0;
    
    for (int i = 0; i < length; ++i) {
        // Convert character digit to integer
        int digit = numStr[i] - '0';
        
        // Apply sign base on the position index
        if (i % 2 == 0) {
            sum += digit; // Positive for even index
        } else {
            sum -= digit; // Negative for odd index
        }
    }
    return sum;
}

// Example usage
int main() {
    int n = 521;
    cout << "The alternating digit sum of " << n << " is: " << alternatingDigitSum(n) << endl;
    return 0;
}

Time Complexity

• Time complexity: (O(d)) where (d) is the number of digits in n. The conversion of n to a string and the iteration through each digit both operate within linear time relative to the number of digits.
• Space complexity: (O(1)) ignoring the space required to hold the input number since the function uses a constant amount of additional space regardless of the input size. The string representation doesn’t change the asymptotic complexity, but it does take up some additional linear space (O(d)) if considered.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?