Find Factorial
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
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.recursion;
import java.util.*;
/ * Problem: Find Factorial * Group: 07. Recursion */ / * ============================================================================================ * PROBLEM: Find Factorial! * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Write a program to find the factorial of the given number A using recursion. * * Definition: * The factorial of a non-negative integer N, denoted by N!, is the product of all positive * integers less than or equal to N. * By convention, 0! = 1. * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Let F(n) be the factorial of n. * * Recurrence Relation: * F(n) = n * F(n - 1) for n > 0 * * Base Case (Stopping Condition): * F(0) = 1 * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 0 <= A <= 12 * * Time Complexity: * O(A) - We make A recursive calls. * * Space Complexity: * O(A) - Stack depth is proportional to A. * * Critical Optimization / Data Type Note: * The constraint is capped at 12 because 13! equals 6,227,020,800, which exceeds the * maximum value of a standard 32-bit signed integer (2,147,483,647). * - For A <= 12, 'int' is sufficient. * - For A >= 13, 'long' is required. * - For A >= 21, 'BigInteger' is required. * Given the problem returns an 'int', the input is strictly limited to A <= 12. * * --------------------- * 4. Input / Output Format * --------------------- * Input: * - A single integer A. * * Output: * - Return an integer denoting A!. * * --------------------- * 5. Examples * --------------------- * Input 1: * A = 4 * Output 1: * 24 * Explanation: 4! = 4 * 3 * 2 * 1 = 24 * * Input 2: * A = 1 * Output 2: * 1 * Explanation: 1! = 1 * * ============================================================================================ */ public class FindFactorial { public int solve(int A) { // TODO: Implement solution return 0; } }