Home | Projects | Notes > Problem Solving > LC - E - 258. Add Digits

LC - E - 258. Add Digits

Solutions in C++

Solution 1

This solution uses iteration.

Complexity Analysis:

• $T=O(?)$$T = O(?)$ where $n$$n$ is the number of digits in the given integer num (Analysis needed!)

• $S=O(1)$$S = O(1)$ as no additional memory is needed

Solution:

xxxxxxxxxx
20
1
class Solution {
2
public:
3
    int addDigits(int num) {
4
        int sum = 0;
5

6
        while (num > 9)
7
        {
8
            while (num > 0)
9
            {
10
                sum += num % 10;
11
                num /= 10;
12
            }
13

14
            num = sum;
15
            sum = 0;
16
        }
17

18
        return num;
19
    }
20
};

Solution 2

This solution uses iteration. Notice how this solution improves the Solution 1 in the time complexity.

Complexity Analysis:

• $T=O(n)$$T = O(n)$ where $n$$n$ is the number of digits in the given integer num

• $S=O(1)$$S = O(1)$ as no additional memory is needed

Solution:

xxxxxxxxxx
20
1
class Solution {
2
public:
3
    int addDigits(int num) {
4
        int sum = 0;
5

6
        while (num > 0)
7
        {
8
            sum += num % 10;
9
            num /= 10;
10
            
11
            if (num == 0 && sum > 9)
12
            {
13
                num = sum;
14
                sum = 0;
15
            }
16
        }
17

18
        return sum;
19
    }
20
};