Find mathematical patterns through observing test cases.

Problem

2544. Alternating Digit Sum

https://leetcode.cn/problems/alternating-digit-sum/

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.

Iterate through string

Solution thinking

1. convert int param to string;
2. iterate string char by char;
3. accumulate sum with specified sign;
4. update sign in loop;

Code

1
2
3
4
5
6
7
8
9

func alternateDigitSum(n int) int {
	nStr := strconv.Itoa(n)
	sum, sign := 0, 1
	for i := range nStr {
		sum += sign * int(nStr[i]-'0')
		sign = -sign
	}
	return sum
}

Complexity analysis

Time

We need to iterate int n with log(n)’s time complexity;

Space

Used an extra string with O(logn)’s length。

Optimizaiton with math solution

Solution thinking

Closely examine the solution mentioned above, the reason why we used an extra string is we want to iterate the n from higher position(significant bit) to lower position.

Another way to iterate the n’s position is using the remainder (modulus) operation as an approach.

BUT, this way leads to a new question: we need to determine the sign.

By observing the test cases, we can find the mathematical patterns: the sign differs between the oddness or evenness of the number of digits in a specific number n.

As illustrated in above picture, we can count the number of digits in n. And for even number, we can just calculate the opposite result sum.

For code simplicity, we can multiply -sign at the end.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func alternateDigitSum(n int) int {
	sum, sign := 0, 1
	for n > 0 {
		sum += sign * (n % 10)
		n /= 10
		sign = -sign
	}
	// n的位数为奇数时，从最低位开始到最高位sign是对称的
	// n的位数为偶数时，从最低位开始到最高位sign 与 从最高位到最低位sign 相反，因此最后乘以-1
	return sum * -sign
}

Complexity analysis

Time

Time complexity is O(log(n)).

Space

In this solution, there is no extra variable. That is the optimization point.

Space complexity is O(1).

Summary

At this point, the question is solved.

By solving this problem, we find the mathematical patterns through observing test cases.

• odd n: sign to left == sign to right
• even n: sign to left == opposite(sign to right)

Observing test cases is so IMPORTANT!