grid47 Exploring patterns and algorithms
Oct 12, 2024
4 min read
Solution to LeetCode 258: Add Digits Problem
Given a non-negative integer num, repeatedly add all of its digits until the result has only one digit, and return it.
Problem
Approach
Steps
Complexity
Input: The input consists of a non-negative integer num.
Example: For example, num = 56.
Constraints:
• 0 <= num <= 231 - 1
Output: Return the resulting single-digit number after summing the digits of num repeatedly.
Example: For num = 56, the output is 2.
Constraints:
• The result should be a single-digit number.
Goal: The goal is to reduce the number num by repeatedly summing its digits until it becomes a single-digit number.
Steps:
• 1. Initialize a variable to hold the sum of digits.
• 2. While the number has more than one digit, sum its digits and update the number.
• 3. Once the number has only one digit, return it.
Goal: The input num is guaranteed to be a non-negative integer between 0 and 2^31 - 1.
Steps:
• 0 <= num <= 231 - 1
Assumptions:
• The input is always a non-negative integer.
• Input: For num = 56, the output is 2.
• Explanation: We repeatedly sum the digits of 56: 5 + 6 = 11, and then 1 + 1 = 2, which is a single digit.
Approach: The approach is to repeatedly sum the digits of the number num until we get a result that is a single-digit number. This can be done by breaking the number down and summing the digits in each iteration.
Observations:
• We can repeatedly break the number down into its individual digits, sum them, and repeat the process until we get a single-digit result.
• To achieve O(1) runtime, we can use properties of numbers in modular arithmetic to avoid loops or recursion.
Steps:
• 1. Initialize a variable to store the sum of the digits.
• 2. While the number is greater than 9, calculate the sum of its digits and update the number.
• 3. Once the number becomes a single digit, return it.
Empty Inputs:
• There are no empty inputs as the input num will always be a non-negative integer.
Large Inputs:
• If the number is very large, the sum of its digits will eventually be reduced to a single-digit number.
Special Values:
• If num is 0, the result will be 0.
Constraints:
• The solution should work for numbers up to 231 - 1.
intaddDigits(int num) {
int res =0;
while(num >9) {
while(num >0) {
res += num %10;
num /=10;
}
num = res;
res =0;
}
return num;
}
1 : Function Definition
intaddDigits(int num) {
Defines the function `addDigits`, which takes an integer `num` as input and returns the resulting single-digit sum after repeatedly summing the digits of the number.
2 : Result Initialization
int res =0;
Initializes the variable `res` to store the sum of digits during each iteration of the inner loop.
3 : Outer Loop Check
while(num >9) {
Checks if the number has more than one digit. If `num` is greater than 9, the process continues to sum the digits.
4 : Inner Loop for Digit Summing
while(num >0) {
This inner loop processes each digit of `num` by extracting and adding them to `res`. It continues as long as `num` is greater than 0.
5 : Add Current Digit to Result
res += num %10;
Adds the last digit of `num` (obtained using the modulo operation) to `res`.
6 : Remove Last Digit
num /=10;
Removes the last digit of `num` by dividing it by 10.
7 : Reset and Repeat with Sum
num = res;
Sets `num` to the value of `res` (the sum of digits) for the next iteration of the outer loop.
8 : Reset Result for Next Iteration
res =0;
Resets `res` to 0 for the next iteration, to start fresh for summing the digits of the next `num`.
9 : Return Result
return num;
Returns the final result, which is the single digit obtained after repeatedly summing the digits of the original `num`.
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: The solution can be optimized to O(1) using a mathematical trick based on the digital root.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) as we only need a constant amount of space.
