Sum Of Digits

Logical Breakdown

• [ ] Subproblem Identification:
• [ ] Optimal Substructure:
• [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
• [ ] Optimization: (Matrix Exponentiation if 'A' is huge)

---

Mathematical Rigor

State Definition

Let \(dp[i]\) be the state for the \(i\)-th subproblem.

Recurrence Relation

\[ dp[i] = ... \]

---

Visualization

graph TD A["Current State"] --> B["Previous State 1"] A --> C["Previous State 2"]

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Iterative DP	\(O(N)\)	\(O(1)\)

---

Code Reference

package com.dsa.recursion;

import java.util.*;

/ * Problem: Sum Of Digits * Group: 07. Recursion */ / * ============================================================================================ * PROBLEM: Sum of Digits! * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given a number A, find the sum of its digits using recursion. * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Let F(n) be the sum of the digits of integer n. * * To obtain the sum, we can isolate the last digit and add it to the sum of the remaining digits. * - The last digit is obtained by n % 10. * - The remaining digits are obtained by integer division n / 10. * * Recurrence Relation: * F(n) = (n % 10) + F(n / 10) * * Base Case (Stopping Condition): * F(0) = 0 * (When the number becomes 0, there are no digits left to add). * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 1 <= A <= 10^9 * * Time Complexity: * O(log_10 A) - The number of recursive calls is equal to the number of digits in A. * For A = 10^9, this is approx 10 operations, which is extremely fast. * * Space Complexity: * O(log_10 A) - The recursion stack depth is equal to the number of digits. * * --------------------- * 4. Input / Output Format * --------------------- * Input: * - A single integer A. * * Output: * - Return an integer denoting the sum of the digits of A. * * --------------------- * 5. Examples * --------------------- * Input 1: * A = 46 * Output 1: * 10 * Explanation: 4 + 6 = 10 * * Input 2: * A = 11 * Output 2: * 2 * Explanation: 1 + 1 = 2 * * ============================================================================================ */ public class SumOfDigits { public int solve(int A) { // TODO: Implement solution return 0; }

public int sumOfDigits(int i) {
    return 1;
}

}