Find Fibonacci II
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 Fibonacci II * Group: 07. Recursion */ / * ============================================================================================ * PROBLEM: Find Fibonacci - II * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * The Fibonacci numbers are a sequence of integers where every number after the first two * is the sum of the two preceding ones. * * The sequence starts: 0, 1, 1, 2, 3, 5, 8, 13, 21... * * Task: * Given a number A, find and return the Ath Fibonacci Number using recursion. * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Let F(n) be the nth Fibonacci number. * * Recurrence Relation: * F(n) = F(n-1) + F(n-2) * * Base Cases (Stopping Conditions): * 1. n = 0 : F(0) = 0 * 2. n = 1 : F(1) = 1 * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 0 <= A <= 20 * * Time Complexity: * - Naive Recursion: O(2^A) (exponential). * - Since A is small (<= 20), 2^20 approx 10^6 operations, which fits well within standard time limits (1 sec). * * Space Complexity: * - O(A) due to the recursion stack depth. * * Optimization Note: * If A were large (e.g., A > 100), naive recursion would TLE (Time Limit Exceeded). * In that scenario, we would use: * 1. Dynamic Programming / Memoization: O(A) * 2. Matrix Exponentiation: O(log A) [Required for A > 10^6] * Given A <= 20, standard recursion is sufficient and required by the problem statement. * * --------------------- * 4. Input / Output Format * --------------------- * Input: * - A single integer A. * * Output: * - Return the Ath term of the Fibonacci sequence. * * --------------------- * 5. Examples * --------------------- * Input 1: * A = 2 * Output 1: * 1 * Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1 * * Input 2: * A = 9 * Output 2: * 34 * Explanation: The 9th term in the sequence 0, 1, 1, 2, 3... is 34. * * ============================================================================================ */ public class FindFibonacciII { public int solve(int A) { // TODO: Implement solution return 0; } }