Problem Statement:-
Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.
Link: https://leetcode.com/problems/add-digits/description/
Problem Explanation with examples:-
Example 1
Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2
Since 2 has only one digit, return it.
Example 2
Input: num = 0
Output: 0
Explanation: It is already in single digit.
Constraints
0 <= num <= 2<sup>31</sup> - 1
Intuition:-
We will keep adding the digits of the number till we get a single digit number.
In another way, we can use the fact that the sum of digits of a number is equal to the remainder of the number divided by 9.
Solution:-
Take a while loop and keep running it till the length of the number is greater than 1.
In the while loop, we will add the digits of the number and update the number.
Finally, we will return the number after the while loop.
For the 2nd approach, if the number is 0, then we will return 0.
If the number is divisible by 9, then we will return 9.
If the number is not divisible by 9, then we will return the remainder of the number divided by 9.
Code:-
JAVA Solution 1
class Solution {
public int addDigits(int num) {
while (String.valueOf(num).length() > 1) {
int sum = 0;
String numStr = Integer.toString(num);
for (int i = 0; i < numStr.length(); i++) {
sum += Character.getNumericValue(numStr.charAt(i));
}
num = sum;
}
return num;
}
}
JAVA Solution 2
class Solution {
public int addDigits(int num) {
if(num==0) return num;
return (num%9 == 0)?9:(num%9);
}
}
Python Solution 1
class Solution:
def addDigits(self, num: int) -> int:
while len(str(num)) > 1:
num = sum(map(int,list(str(num))))
return num
Python Solution 2
class Solution:
def addDigits(self, num: int) -> int:
if num == 0:
return num
return 9 if num % 9 == 0 else num % 9
Complexity Analysis:-
TIME:-
The time complexity of the 1st code is O(n) where n is the number of digits in the number as we are iterating over the digits of the number. The time complexity of the 2nd code is O(1) as we are just doing constant time operations.
SPACE:-
The space complexity of both the code is O(1) as we are not using any extra space.