Given a positive integer N representing the number of disks in the Tower of Hanoi, the task is to solve the Tower of Hanoi puzzle using Binary representations.
Examples:
Input: N = 3
Output:
Move the 1 disk to next circular right rod
Move the 2 disk to next circular right rod
Move the 1 disk to next circular right rod
Move the 3 disk to next circular right rod
Move the 1 disk to next circular right rod
Move the 2 disk to next circular right rod
Move the 1 disk to next circular right rodInput: N = 4
Output:
Move the 1 disk to next circular right rod
Move the 2 disk to next circular right rod
Move the 1 disk to next circular right rod
Move the 3 disk to next circular right rod
Move the 1 disk to next circular right rod
Move the 2 disk to next circular right rod
Move the 1 disk to next circular right rod
Move the 4 disk to next circular right rod
Move the 1 disk to next circular right rod
Move the 2 disk to next circular right rod
Move the 1 disk to next circular right rod
Move the 3 disk to next circular right rod
Move the 1 disk to next circular right rod
Move the 2 disk to next circular right rod
Move the 1 disk to next circular right rod
Approach: The given problem can be solved based on the following observations:
- It can be observed that to move the Nth disk, (N – 1)th disk needs to be moved. Therefore, to move (N – 1)th disk, (N – 2)th disk needs to be moved. This process goes on recursively.
- The above procedure is similar to setting the rightmost unset bit as it requires to set all the bits to right of it first.
- Therefore, the idea is to print all the intermediate steps, every time setting the right most bit by incrementing the current number by 1.
Follow the steps below to solve the problem:
- Initialize an array, say counter[], of size N, to store the current state of the problem.
- Iterate over the range [0, 2N – 1], set the rightmost unset bit, and unset all the bits to the right of it.
- In every iteration of the above step, print the position of the rightmost unset bit as the number of the disk which is to be moved.
Below is the implementation of the above approach:
C++
// C++ program for the above approachÂ
#include <bits/stdc++.h>using namespace std;Â
// Function to increment binary counterint increment(int* counter, int n){Â Â Â Â int i = 0;Â
    while (true) {Â
        // Stores the Bitwise XOR of        // the i-th bit of N and 1        int a = counter[i] ^ 1;Â
        // Stores the Bitwise AND of        // the i-th bit of N and 1        int b = counter[i] & 1;Â
        // Swaps the i-th bit of N        counter[i] = a;Â
        // If b is equal to zero        if (b == 0)            break;Â
        // Increment i by 1        i = i + 1;    }Â
    // Return i    return i;}Â
// Function to print order of movement// of disks across three rods to place// all disks on the third rod from the// first rodvoid TowerOfHanoi(int N){    // Stores the binary representation    // of a state    int counter[N] = { 0 };Â
    // Traverse the range [0, 2^N - 1]    for (int step = 1;         step <= pow(2, N) - 1; step++) {Â
        // Stores the position of the        // rightmost unset bit        int x = increment(counter, N) + 1;Â
        // Print the Xth bit        cout << "Move disk " << x             << " to next circular"             << " right rod \n";    }}Â
// Driver Codeint main(){Â Â Â Â int N = 3;Â Â Â Â TowerOfHanoi(N);Â
    return 0;} |
Java
// Java program for the above approachimport java.util.*;Â
class GFG{Â Â Â Â Â // Function to increment binary counterstatic int increment(int[] counter, int n){Â Â Â Â int i = 0;Â
    while (true)     {                 // Stores the Bitwise XOR of        // the i-th bit of N and 1        int a = counter[i] ^ 1;Â
        // Stores the Bitwise AND of        // the i-th bit of N and 1        int b = counter[i] & 1;Â
        // Swaps the i-th bit of N        counter[i] = a;Â
        // If b is equal to zero        if (b == 0)            break;Â
        // Increment i by 1        i = i + 1;    }Â
    // Return i    return i;}Â
// Function to print order of movement// of disks across three rods to place// all disks on the third rod from the// first rodstatic void TowerOfHanoi(int N){         // Stores the binary representation    // of a state    int[] counter=new int[N];Â
    // Traverse the range [0, 2^N - 1]    for(int step = 1;            step <= Math.pow(2, N) - 1;             step++)     {Â
        // Stores the position of the        // rightmost unset bit        int x = increment(counter, N) + 1;Â
        // Print the Xth bit        System.out.println("Move disk " + x +                           " to next circular" +                           " right rod");    }}Â
// Driver codepublic static void main(String[] args) {         // Given inputs    int N = 3;         TowerOfHanoi(N);}}Â
// This code is contributed by offbeat |
Python3
# Python program for the above approachimport mathÂ
# Function to increment binary counterdef increment(counter, n):    i = 0         while (True):                 # Stores the Bitwise XOR of        # the i-th bit of N and 1        a = counter[i] ^ 1                 # Stores the Bitwise AND of        # the i-th bit of N and 1        b = counter[i] & 1                 # Swaps the i-th bit of N        counter[i] = a                 # If b is equal to zero        if (b == 0):            break                 # Increment i by 1         i = i + 1    return iÂ
# Function to print order of movement# of disks across three rods to place# all disks on the third rod from the# first rod   def TowerOfHanoi(N):         # Stores the binary representation    # of a state    counter=[0 for i in range(N)]         # Traverse the range [0, 2^N - 1]    for step in range(1,int(math.pow(2,N))):                 # Stores the position of the        # rightmost unset bit        x = increment(counter, N) + 1                 #Print the Xth bit        print("Move disk ",x," to next circular"," right rod")Â
# Driver codeN = 3TowerOfHanoi(N)Â Â Â Â Â Â Â Â Â # This code is contributed by rag2127 |
C#
// C# program for the above approachusing System;class GFG {       // Function to increment binary counter    static int increment(int[] counter, int n)    {        int i = 0;        while (true)         {Â
            // Stores the Bitwise XOR of            // the i-th bit of N and 1            int a = counter[i] ^ 1;Â
            // Stores the Bitwise AND of            // the i-th bit of N and 1            int b = counter[i] & 1;Â
            // Swaps the i-th bit of N            counter[i] = a;Â
            // If b is equal to zero            if (b == 0)                break;Â
            // Increment i by 1            i = i + 1;        }Â
        // Return i        return i;    }Â
    // Function to print order of movement    // of disks across three rods to place    // all disks on the third rod from the    // first rod    static void TowerOfHanoi(int N)    {               // Stores the binary representation        // of a state        int[] counter = new int[N];Â
        // Traverse the range [0, 2^N - 1]        for (int step = 1;             step <= (int)(Math.Pow(2, N) - 1); step++)        {Â
            // Stores the position of the            // rightmost unset bit            int x = increment(counter, N) + 1;Â
            // Print the Xth bit            Console.WriteLine("Move disk " + x                              + " to next circular"                              + " right rod ");        }    }Â
    // Driver Code    public static void Main()    {        int N = 3;        TowerOfHanoi(N);    }}Â
// This code is contributed by ukasp. |
Javascript
<script>// Javascript implementation for the above approachÂ
// Function to increment binary counterfunction increment(counter, n){Â Â Â Â let i = 0;Â
    while (true)     {                 // Stores the Bitwise XOR of        // the i-th bit of N and 1        let a = counter[i] ^ 1;Â
        // Stores the Bitwise AND of        // the i-th bit of N and 1        let b = counter[i] & 1;Â
        // Swaps the i-th bit of N        counter[i] = a;Â
        // If b is equal to zero        if (b == 0)            break;Â
        // Increment i by 1        i = i + 1;    }Â
    // Return i    return i;}Â
// Function to print order of movement// of disks across three rods to place// all disks on the third rod from the// first rodfunction TowerOfHanoi(N){         // Stores the binary representation    // of a state    let counter= Array.from({length: N}, (_, i) => 0);Â
    // Traverse the range [0, 2^N - 1]    for(let step = 1;            step <= Math.pow(2, N) - 1;             step++)     {Â
        // Stores the position of the        // rightmost unset bit        let x = increment(counter, N) + 1;Â
        // Print the Xth bit        document.write("Move disk " + x +                           " to next circular" +                           " right rod" + "<br/>");    }}Â
    // Driver Code         // Given inputs    let N = 3;         TowerOfHanoi(N);Â
// This code is contributed by sanjoy_62.</script> |
Output:Â
Move disk 1 to next circular right rod Move disk 2 to next circular right rod Move disk 1 to next circular right rod Move disk 3 to next circular right rod Move disk 1 to next circular right rod Move disk 2 to next circular right rod Move disk 1 to next circular right rod
Â
Time Complexity: O(N * 2N)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized based on the observations that for M over the range [1, 2N – 1], source rod is equal to (m & (m – 1)) % 3 and the destination rod is equal to (m | (m – 1) + 1) % 3. Therefore, the idea is to iterate over the range [1, 2N – 1] and print the value of (i & (i – 1))%3 as source rod and (i | (i – 1) + 1)%3 as destination rod.
Below is the implementation of the above approach:
C++
// C++ program for the above approachÂ
#include <bits/stdc++.h>using namespace std;Â
// Function to print order of movement// of N disks across three rods to place// all disks on the third rod from the// first-rod using binary representationvoid TowerOfHanoi(int N){Â Â Â Â // Iterate over the range [0, 2^N - 1]Â Â Â Â for (int x = 1;Â Â Â Â Â Â Â Â Â x <= pow(2, N) - 1; x++) {Â
        // Print the movement        // of the current rod        cout << "Move from Rod "             << ((x & x - 1) % 3 + 1)             << " to Rod "             << (((x | x - 1) + 1) % 3 + 1)             << endl;    }}Â
// Driver Codeint main(){Â Â Â Â int N = 3;Â Â Â Â TowerOfHanoi(N);Â Â Â Â return 0;} |
Java
// Java program for the above approachclass GFG{     // Function to print order of movement// of N disks across three rods to place// all disks on the third rod from the// first-rod using binary representationstatic void TowerOfHanoi(int N){         // Iterate over the range [0, 2^N - 1]    for(int x = 1;            x <= Math.pow(2, N) - 1; x++)    {                 // Print the movement        // of the current rod        System.out.print("Move from Rod " +                          ((x & x - 1) % 3 + 1) + " to Rod " +                          (((x | x - 1) + 1) % 3 + 1) + "\n");    }}Â
// Driver Codepublic static void main (String[] args){Â Â Â Â int N = 3;Â Â Â Â Â Â Â Â Â TowerOfHanoi(N);}}Â
// This code is contributed by jana_sayantan |
Python3
# Python program for the above approachimport mathÂ
# Function to print order of movement# of N disks across three rods to place# all disks on the third rod from the# first-rod using binary representationdef TowerOfHanoi(N):         # Iterate over the range [0, 2^N - 1]    for x in range(1,int(math.pow(2, N)) ):                 # Print the movement        # of the current rod        print("Move from Rod " ,                         ((x & x - 1) % 3 + 1) , " to Rod " ,                         (((x | x - 1) + 1) % 3 + 1) )Â
# Driver CodeN=3TowerOfHanoi(N)Â
# This code is contributed by avanitrachhadiya2155 |
C#
// C# program for the above approachusing System;Â
class GFG{     // Function to print order of movement// of N disks across three rods to place// all disks on the third rod from the// first-rod using binary representationstatic void TowerOfHanoi(int N){         // Iterate over the range [0, 2^N - 1]    for(int x = 1;            x <= Math.Pow(2, N) - 1; x++)    {                 // Print the movement        // of the current rod        Console.Write("Move from Rod " +                          ((x & x - 1) % 3 + 1) + " to Rod " +                          (((x | x - 1) + 1) % 3 + 1) + "\n");    }}Â
// Driver Codestatic void Main(){Â Â Â Â int N = 3;Â Â Â Â Â Â Â Â Â TowerOfHanoi(N);}}Â
// This code is contributed by SoumikMondal |
Javascript
<script>Â
// Javascript program for the above approachÂ
// Function to print order of movement// of N disks across three rods to place// all disks on the third rod from the// first-rod using binary representationfunction TowerOfHanoi(N){Â Â Â Â // Iterate over the range [0, 2^N - 1]Â Â Â Â for (let x = 1;Â Â Â Â Â Â Â Â Â x <= Math.pow(2, N) - 1; x++) {Â
        // Print the movement        // of the current rod        document.write("Move from Rod "             + ((x & x - 1) % 3 + 1)             + " to Rod "             + (((x | x - 1) + 1) % 3 + 1)             + "<br>");    }}Â
// Driver Code    let N = 3;    TowerOfHanoi(N);Â
</script> |
Output:Â
Move from Rod 1 to Rod 3 Move from Rod 1 to Rod 2 Move from Rod 3 to Rod 2 Move from Rod 1 to Rod 3 Move from Rod 2 to Rod 1 Move from Rod 2 to Rod 3 Move from Rod 1 to Rod 3
Â
Time Complexity: O(2N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
