Tower Of Hanoi

Tower of Hanoi is a mathematical problem with the following conditions:

  • There are three towers
  • There may be n number of rings present
  • The rings are of different sizes
  • Only one disk can be moved at a time
  • Any disk can only be moved on the top of a bigger disk
  • Only the top disk can be removed

Explanation

Let us look at how this problem can be handled when we have two disks

Tower Of Hanoi Explained

We move the top(small) disk onto the next tower after which we move the second disk to the third tower and then eventually shift the first disk as well on to the third tower. (3 moves)

Assumption: The disks are initially sorted

Similarly when we work with 3 disks. We would need 7 steps to shift all of them to the third ring.

  • Disk 1 moved from 1 to 3Tower Of Hanoi
  • Now, Disk 2 moved from 1 to 2Tower Of Hanoi
  • Disk 1 moved from 3 to 2Tower Of Hanoi
  • Disk 3 moved from 1 to 3Tower Of Hanoi
  • Now, Disk 1 moved from 2 to 1
  • Disk 2 moved from 2 to 3
  • Disk 1 moved from 1 to 3

We are thus moving n-1 disks on to the second tower, the last disk to the third tower and n-1 disks onto the first disk thus completing the shift.

Let us now look at a recursive implementation of the same.

JAVA Program for Tower Of Hanoi

public class hanoi
{
  public static void hanoi(int n,char from,char mid,char to)
  {
    if(n==1)
    {
      //Moving disk1 on to the first rod
      System.out.println("Moving disk "+n+"From rod:"+from+"To Rod"+to);
      return;
    }
    //Moving n-1 disks to the second rod
    hanoi(n-1,from,to,mid);
    System.out.println("Moving disk "+n+"From rod:"+from+"To Rod"+to);
    //Moving the disks on top of already moved first disk
    hanoi(n-1,mid,from,to);
  }
  public static void main(String args[])
  {
    int n=3;
    hanoi(n,'A','B','C');
  }
}

C++ Program for Tower Of Hanoi

#include<iostream>
using namespace std;
  void hanoi(int n,char from,char mid,char to)
  {
    if(n==1)
    {
      //Moving disk1 on to the first rod
      cout<<"Moving disk "<< n <<"From rod:"<< from <<" To Rod:"<< to <<endl;
      return;
    }
    //Moving n-1 disks to the second rod
    hanoi(n-1,from,to,mid);
    cout<<"Moving disk "<< n <<"From rod:"<< from <<" To Rod:"<< to <<endl;
    //Moving the disks on top of already moved first disk
    hanoi(n-1,mid,from,to);
  }
  int main()
  {
    int n=4;
    hanoi(n,'A','B','C');
  }
Moving disk 1From rod: A To Rod: B
Moving disk 2From rod:A To Rod:C
Moving disk 1From rod:B To Rod:C
Moving disk 3From rod: A To Rod: B
Moving disk 1From rod:C To Rod:A
Moving disk 2From rod:C To Rod:B
Moving disk 1From rod: A To Rod: B
Moving disk 4From rod:A To Rod:C
Moving disk 1From rod:B To Rod:C
Moving disk 2From rod: B To Rod: A
Moving disk 1From rod:C To Rod:A
Moving disk 3From rod:B To Rod:C
Moving disk 1From rod: A To Rod: B
Moving disk 2From rod:A To Rod:C
Moving disk 1From rod:B To Rod:C

Conclusion for Tower Of Hanoi

We thus come to the conclusion:

15 moves for 4 disks

31 moves for 5 disks

Thus, we come to the conclusion that for n disks we need to make (2^n)-1 moves.

2 disks=(2*2)-1=2 moves

3 disks=(2^3)-1=7 moves

4 disks=(2^4)-1=15 moves

and so on.

Complexity Analysis for Tower Of Hanoi

Time Complexity

Recursive Equation:  T(n) = 2T(n-1) + 1

T(n)= O( 2^{(n+1)} - 1), or you can say O(2^n) which is exponential

Space Complexity

T(n) = T(n-1) + k
T(0) = k
T(1) = 2k
T(2) = 3k
T(3) = 4k
So the space complexity is O(n).

References

Merge K Sorted Linked Lists

Merge K sorted linked lists problem is so famous as per the interview point of view. This question asks so many times in big companies like Google, Microsoft, Amazon, etc.  As the name suggests we’ve been provided with k sorted linked lists. We have to merge them together into a …

Read moreMerge K Sorted Linked Lists

Maximum Subarray

In the Maximum Subarray problem we have given an integer array nums, find the contiguous sub array which has the largest sum and print the maximum sum subarray value. Example Input nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4} Output 6 Algorithm The goal is to find …

Read moreMaximum Subarray

Merge Sort

What is merge sort? Merge Sort is a Recursive Procedure. It is also a divide and conquers algorithm. Now we need to know what divide and conquer algorithm is? It’s a type of procedure in which we divide the problem into subproblems and divide them until we find the shortest …

Read moreMerge Sort

Longest Common Prefix using Divide and Conquer

Problem Statement In the “Longest Common Prefix using Divide and Conquer ” problem, we have given an integer n and n strings. Write a program that will print the longest common prefix. If there is no common prefix then print “-1”. Input Format The first line contains an integer n. …

Read moreLongest Common Prefix using Divide and Conquer

Find the point where a monotonically increasing function becomes positive first time

Problem Statement In the “Find the point where a monotonically increasing function becomes positive first time” we have given a function “int f(unsigned int x)” which takes a non-negative integer ‘x’ as input and returns an integer as output. The function is monotonically increasing with respect to the value of x, i.e., the …

Read moreFind the point where a monotonically increasing function becomes positive first time

Maximum Subarray Sum using Divide and Conquer

Problem Statement In the “Maximum Subarray Sum using Divide and Conquer” problem we have given an array of both positive and negative integers. Write a program that will find the largest sum of the contiguous subarray. Input Format The first line containing an integer N. Second-line containing an array of …

Read moreMaximum Subarray Sum using Divide and Conquer