algoadvance

Leetcode 258. Add Digits

Problem Statement

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

Example

Input: num = 38
Output: 2
Explanation: The process is as follows: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Clarifying Questions

  1. Q: What is the range of input value for num?
    • A: The input integer num can range from 0 to 2^31 - 1.
  2. Q: Can the input number be negative?
    • A: According to the problem description, num is a non-negative integer.
  3. Q: Do we need to handle very large numbers efficiently?
    • A: Yes, even for very large numbers the solution should be efficient.

Strategy

A straightforward strategy involves repeatedly summing the digits of the number until a single digit remains. However, there is a well-known mathematical shortcut for this problem using properties of numbers and modular arithmetic (digital root problem).

The digital root can be directly calculated using:

This is based on the property that any number modulo 9 yields the same result as the sum of its digits modulo 9.

Code

#include <iostream>
using namespace std;

class Solution {
public:
    int addDigits(int num) {
        if (num == 0) return 0;
        if (num % 9 == 0) return 9;
        return num % 9;
    }
};

int main() {
    Solution solution;
    int num = 38;
    cout << "The result of adding digits for " << num << " is: " << solution.addDigits(num) << endl;
    return 0;
}

Explanation

  1. Condition for Zero: If num is 0, then we immediately return 0.
  2. Modulo Condition: If num is divisible by 9, the result should be 9 (except when num is 0).
  3. Direct Modulo: If none of the above conditions hold, return num % 9.

Time Complexity

The time complexity of this solution is O(1). The reason is that we are using a direct formula to compute the result, which involves constant-time operations. Thus, this method is very efficient and scalable even for the upper bounds of input size constraints.

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