Challenge - 5 Problems
Tower of Hanoi Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of Tower of Hanoi moves for 2 disks
What is the output of the following Tower of Hanoi function call for 2 disks?
DSA C
void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) { if (n == 1) { printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod); return; } towerOfHanoi(n - 1, from_rod, aux_rod, to_rod); printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod); towerOfHanoi(n - 1, aux_rod, to_rod, from_rod); } int main() { towerOfHanoi(2, 'A', 'C', 'B'); return 0; }
Attempts:
2 left
💡 Hint
Remember the recursive steps: move n-1 disks to auxiliary rod, move nth disk to target rod, then move n-1 disks from auxiliary to target rod.
✗ Incorrect
The Tower of Hanoi algorithm moves the top n-1 disks to the auxiliary rod first, then moves the largest disk to the target rod, and finally moves the n-1 disks from the auxiliary rod to the target rod. For 2 disks, the moves are: disk 1 from A to B, disk 2 from A to C, disk 1 from B to C.
🧠 Conceptual
intermediate1:00remaining
Minimum number of moves for Tower of Hanoi
What is the minimum number of moves required to solve the Tower of Hanoi problem with 4 disks?
Attempts:
2 left
💡 Hint
The minimum moves follow the formula 2^n - 1, where n is the number of disks.
✗ Incorrect
The minimum number of moves to solve Tower of Hanoi with n disks is 2^n - 1. For 4 disks, it is 2^4 - 1 = 16 - 1 = 15.
🔧 Debug
advanced1:30remaining
Identify the error in Tower of Hanoi code
What error will the following Tower of Hanoi code produce when called with n=3?
void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
if (n == 0) {
printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod);
return;
}
towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}
Attempts:
2 left
💡 Hint
Check the base case condition and what happens when n reaches 0.
✗ Incorrect
The base case is if (n == 0), which prints "Move disk 1" incorrectly instead of handling n==1 properly. This leads to incorrect move descriptions and order, but the recursion terminates normally without stack overflow or other runtime errors.
❓ Predict Output
advanced2:00remaining
Output of Tower of Hanoi moves for 3 disks
What is the output of the Tower of Hanoi function call for 3 disks?
DSA C
void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) { if (n == 1) { printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod); return; } towerOfHanoi(n - 1, from_rod, aux_rod, to_rod); printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod); towerOfHanoi(n - 1, aux_rod, to_rod, from_rod); } int main() { towerOfHanoi(3, 'A', 'C', 'B'); return 0; }
Attempts:
2 left
💡 Hint
Trace the recursive calls carefully, moving n-1 disks to auxiliary, then nth disk to target, then n-1 disks from auxiliary to target.
✗ Incorrect
The Tower of Hanoi algorithm for 3 disks from A to C using auxiliary B produces:
Move disk 1 from rod A to rod C
Move disk 2 from rod A to rod B
Move disk 1 from rod C to rod B
Move disk 3 from rod A to rod C
Move disk 1 from rod B to rod A
Move disk 2 from rod B to rod C
Move disk 1 from rod A to rod C
🧠 Conceptual
expert1:00remaining
Time complexity of Tower of Hanoi algorithm
What is the time complexity of the Tower of Hanoi algorithm for n disks?
Attempts:
2 left
💡 Hint
Consider how the number of moves grows as the number of disks increases.
✗ Incorrect
The Tower of Hanoi algorithm requires 2^n - 1 moves, so its time complexity is exponential, O(2^n).