Advertisement

Add Digits - LeetCode 258 Solution

Add Digits - Complete Solution Guide

Add Digits is LeetCode problem 258, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an integer num , repeatedly add all its digits until the result has only one digit, and return it. 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 Constraints: 0 <= num <= 2 31 - 1 Follow up: Could you do it without any loop/recursion in O(1) runtime?

Detailed Explanation

The problem asks you to repeatedly sum the digits of a given integer until a single-digit integer is obtained. For example, if the input is 38, the process would be: 38 -> 3 + 8 = 11 -> 1 + 1 = 2. The function should return 2. The input is a non-negative integer, and the output is a single-digit integer.

Solution Approach

The provided solutions demonstrate two different approaches. The Python solution leverages the mathematical insight that the repeated sum of digits is congruent to the number modulo 9 (except for multiples of 9 which result in 9). This allows for a constant-time solution. The Java, C++, and C solutions use an iterative approach. They repeatedly sum the digits until a single-digit number is reached.

Step-by-Step Algorithm

  1. Step 1 (Iterative Approach): Check if the number is less than 10. If so, return the number as it's already a single digit.
  2. Step 2 (Iterative Approach): If the number is greater than or equal to 10, initialize a sum variable to 0.
  3. Step 3 (Iterative Approach): Extract the last digit using the modulo operator (%) and add it to the sum. Remove the last digit using integer division (/).
  4. Step 4 (Iterative Approach): Repeat Step 3 until the number becomes 0.
  5. Step 5 (Iterative Approach): Assign the sum to the number and repeat from Step 1.
  6. Step 1 (Mathematical Approach): Handle the base case where the input is 0, returning 0.
  7. Step 2 (Mathematical Approach): If the number is a multiple of 9 (num % 9 == 0), return 9.
  8. Step 3 (Mathematical Approach): Otherwise, return the remainder when the number is divided by 9 (num % 9).

Key Insights

  • Insight 1: Recognizing the pattern that the repeated digit sum of a number is congruent to the number modulo 9 (except for multiples of 9 which result in 9).
  • Insight 2: Understanding that a simple iterative approach or a mathematical shortcut can solve this problem efficiently.
  • Insight 3: Handling the edge case of 0 and recognizing that the modulo operation provides an elegant solution for the general case.

Complexity Analysis

Time Complexity: O(1)

Space Complexity: O(1)

Topics

This problem involves: Math, Simulation, Number Theory.

Companies

Asked at: American Express.