Problem Statement
Given a non-negative integer
num
, repeatedly add all its digits until the result has only one digit.
Example:
Input:38
Output: 2 Explanation: The process is like:3 + 8 = 11
,1 + 1 = 2
. Since2
has only one digit, return it.
Follow up:
Could you do it without any loop/recursion in O(1) runtime?
Problem link Could you do it without any loop/recursion in O(1) runtime?
Video Tutorial
You can find the detailed video tutorial hereThought Process
Just do a simple brute force simulation. Unless you know what a digital root is, beforehand solving it in O(1) cannot collect any useful signals from the candidate.Side note:
I am sharing with everyone on this problem just to express how useless this problem is... Honestly if someone ask you to solve this problem in O(1) time in a real interview, rethink joining that company. If you are an interviewer, please do yourself a favor not asking your candidate to solve it in O(1). It's an okay question to ask as a warm up just to calm your candidate down for the brute force solution.
Solutions
Brute force
Keep summing the each digit until the final number is < 10Time Complexity: O(N), N is the length of the digit
Space Complexity: O(1), No extra space is needed
Use the digital root formula
return (num - 1) % 9 + 1
Time Complexity: O(1)Space Complexity: O(1)