Tower Of Hanoi

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: Tower Of Hanoi * Group: 07. Recursion */ / * ============================================================================================ * PROBLEM: Tower of Hanoi * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Solve the classic Tower of Hanoi puzzle with A disks. * - Towers are numbered 1, 2, 3. * - Initial State: All disks are on Tower 1, sorted by size (1 is top/smallest, A is bottom/largest). * - Goal: Move all disks to Tower 3. * * Constraints: * 1. Only one disk can be moved at a time. * 2. A disk cannot be placed on top of a smaller disk. * * Output: * Return a 2D array (or list of moves) of size (2^A - 1) x 3. * Each move is represented as: [disk_number, from_tower, to_tower]. * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Let T(n, source, destination, helper) be the function to move n disks. * * Recurrence Relation: * To move n disks from 'source' to 'destination' using 'helper': * 1. Recursively move top (n-1) disks from 'source' to 'helper'. * (Now, disk n is free to move). * 2. Move disk n from 'source' to 'destination'. * (Record this move). * 3. Recursively move the (n-1) disks from 'helper' to 'destination'. * * Base Case: * If n == 1: * Move disk 1 from 'source' to 'destination'. * Return. * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 1 <= A <= 18 * * Time Complexity: * O(2^A) - The number of moves required is exactly 2^A - 1. * For A = 18, 2^18 = 262,144 moves. This fits within memory and time limits. * * Space Complexity: * O(2^A) - To store the result list. * O(A) - Recursion stack depth. * * --------------------- * 4. Input / Output Format * --------------------- * Input: * - Integer A. * * Output: * - A 2D Data Structure (e.g., ArrayList or int[][]) representing the moves. * * --------------------- * 5. Examples * --------------------- * Input: A = 2 * Goal: Move 2 disks from T1 to T3 using T2. * Steps: * 1. Move disk 1 (top) from T1 -> T2. * 2. Move disk 2 (base) from T1 -> T3. * 3. Move disk 1 (from T2) -> T3. * Output: [[1, 1, 2], [2, 1, 3], [1, 2, 3]] * * ============================================================================================ */ public class TowerOfHanoi { public int solve(int A) { // TODO: Implement solution return 0; }

public ArrayList<int[]> towerOfHanoi(int i) {
    return new ArrayList<>();
}

}