Open In App

Iterative Tower of Hanoi

Last Updated : 22 Dec, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

The Tower of Hanoi is a mathematical puzzle. It consists of three poles and a number of disks of different sizes which can slide onto any pole. The puzzle starts with the disk in a neat stack in ascending order of size in one pole, the smallest at the top thus making a conical shape. The objective of the puzzle is to move all the disks from one pole (say ‘source pole’) to another pole (say ‘destination pole’) with the help of the third pole (say auxiliary pole).

The puzzle has the following two rules:
      1. You can’t place a larger disk onto a smaller disk 
      2. Only one disk can be moved at a time

We’ve already discussed a recursive solution for the Tower of Hanoi. We have also seen that for n disks, a total of  2n – 1 moves are required. 

Iterative Algorithm: 

1. Calculate the total number of moves required i.e. "pow(2, n)
- 1" here n is number of disks.
2. If number of disks (i.e. n) is even then interchange destination
pole and auxiliary pole.
3. for i = 1 to total number of moves:
if i%3 == 1:
legal movement of top disk between source pole and
destination pole
if i%3 == 2:
legal movement top disk between source pole and
auxiliary pole
if i%3 == 0:
legal movement top disk between auxiliary pole
and destination pole

Example: 

Let us understand with a simple example with 3 disks:
So, total number of moves required = 7

1

        S                      A                   D

When i= 1, (i % 3 == 1) legal movement between‘S’ and ‘D’

2

When i = 2,  (i % 3 == 2) legal movement between ‘S’ and ‘A’ 

2

When i = 3, (i % 3 == 0) legal movement between ‘A’ and ‘D’ ’

2

When i = 4, (i % 3 == 1) legal movement between ‘S’ and ‘D’ 

2

When i = 5, (i % 3 == 2) legal movement between ‘S’ and ‘A’

2

When i = 6, (i % 3 == 0) legal movement between ‘A’ and ‘D’ 

2

When i = 7, (i % 3 == 1) legal movement between ‘S’ and ‘D’ 

2

So, after all these destination poles contains all the in order of size. 
After observing above iterations, we can think that after a disk other than the smallest disk is moved, the next disk to be moved must be the smallest disk because it is the top disk resting on the spare pole and there are no other choices to move a disk.

C++




// C++ Program for Iterative Tower of Hanoi using STL
 
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
char rod[]={'S', 'A', 'D'};
vector<stack<int>> stacks(3); // 3 stacks for 3 rods
 
void moveDisk(int a, int b)
{
    if (stacks[b].empty() || (!stacks[a].empty() && stacks[a].top() < stacks[b].top()))
    {
        cout << "Move disk " << stacks[a].top() << " from rod " << rod[a] << " to rod " << rod[b] << "\n";
        stacks[b].push(stacks[a].top());
        stacks[a].pop();
    }
    else
        moveDisk(b, a);
}
 
void towerOfHanoi(int n)
{
    cout << "Tower of Hanoi for " << n << " disks:\n";
 
    int src = 0, aux = 1, dest = 2;
    for (int i = n; i > 0; i--)
        stacks[src].push(i);
 
    int totalMoves = (1 << n) - 1;
    if (n % 2 == 0)
        swap(aux, dest);
 
    for (int i = 1; i <= totalMoves; i++)
    {
        if (i % 3 == 0)
            moveDisk(aux, dest);
        else if (i % 3 == 1)
            moveDisk(src, dest);
        else
            moveDisk(src, aux);
    }
}
 
int main()
{
    int n = 3; // number of disks
    towerOfHanoi(n);
    return 0;
}


C




// C Program for Iterative Tower of Hanoi
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
 
// A structure to represent a stack
struct Stack
{
unsigned capacity;
int top;
int *array;
};
 
// function to create a stack of given capacity.
struct Stack* createStack(unsigned capacity)
{
    struct Stack* stack =
        (struct Stack*) malloc(sizeof(struct Stack));
    stack -> capacity = capacity;
    stack -> top = -1;
    stack -> array =
        (int*) malloc(stack -> capacity * sizeof(int));
    return stack;
}
 
// Stack is full when top is equal to the last index
int isFull(struct Stack* stack)
{
return (stack->top == stack->capacity - 1);
}
 
// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{
return (stack->top == -1);
}
 
// Function to add an item to stack. It increases
// top by 1
void push(struct Stack *stack, int item)
{
    if (isFull(stack))
        return;
    stack -> array[++stack -> top] = item;
}
 
// Function to remove an item from stack. It
// decreases top by 1
int pop(struct Stack* stack)
{
    if (isEmpty(stack))
        return INT_MIN;
    return stack -> array[stack -> top--];
}
 
//Function to show the movement of disks
void moveDisk(char fromPeg, char toPeg, int disk)
{
    printf("Move the disk %d from \'%c\' to \'%c\'\n",
        disk, fromPeg, toPeg);
}
 
// Function to implement legal movement between
// two poles
void moveDisksBetweenTwoPoles(struct Stack *src,
            struct Stack *dest, char s, char d)
{
    int pole1TopDisk = pop(src);
    int pole2TopDisk = pop(dest);
 
    // When pole 1 is empty
    if (pole1TopDisk == INT_MIN)
    {
        push(src, pole2TopDisk);
        moveDisk(d, s, pole2TopDisk);
    }
 
    // When pole2 pole is empty
    else if (pole2TopDisk == INT_MIN)
    {
        push(dest, pole1TopDisk);
        moveDisk(s, d, pole1TopDisk);
    }
 
    // When top disk of pole1 > top disk of pole2
    else if (pole1TopDisk > pole2TopDisk)
    {
        push(src, pole1TopDisk);
        push(src, pole2TopDisk);
        moveDisk(d, s, pole2TopDisk);
    }
 
    // When top disk of pole1 < top disk of pole2
    else
    {
        push(dest, pole2TopDisk);
        push(dest, pole1TopDisk);
        moveDisk(s, d, pole1TopDisk);
    }
}
 
//Function to implement TOH puzzle
void tohIterative(int num_of_disks, struct Stack
            *src, struct Stack *aux,
            struct Stack *dest)
{
    int i, total_num_of_moves;
    char s = 'S', d = 'D', a = 'A';
 
    //If number of disks is even, then interchange
    //destination pole and auxiliary pole
    if (num_of_disks % 2 == 0)
    {
        char temp = d;
        d = a;
        a = temp;
    }
    total_num_of_moves = pow(2, num_of_disks) - 1;
 
    //Larger disks will be pushed first
    for (i = num_of_disks; i >= 1; i--)
        push(src, i);
 
    for (i = 1; i <= total_num_of_moves; i++)
    {
        if (i % 3 == 1)
        moveDisksBetweenTwoPoles(src, dest, s, d);
 
        else if (i % 3 == 2)
        moveDisksBetweenTwoPoles(src, aux, s, a);
 
        else if (i % 3 == 0)
        moveDisksBetweenTwoPoles(aux, dest, a, d);
    }
}
 
// Driver Program
int main()
{
    // Input: number of disks
    unsigned num_of_disks = 3;
 
    struct Stack *src, *dest, *aux;
 
    // Create three stacks of size 'num_of_disks'
    // to hold the disks
    src = createStack(num_of_disks);
    aux = createStack(num_of_disks);
    dest = createStack(num_of_disks);
 
    tohIterative(num_of_disks, src, aux, dest);
    return 0;
}


Java




// Java program for iterative
// Tower of Hanoi
class TOH{
     
// A structure to represent a stack
class Stack
{
    int capacity;
    int top;
    int array[];
}
 
// Function to create a stack of given capacity.
Stack createStack(int capacity)
{
    Stack stack = new Stack();
    stack.capacity = capacity;
    stack.top = -1;
    stack.array = new int[capacity];
    return stack;
}
 
// Stack is full when the top is equal
// to the last index
boolean isFull(Stack stack)
{
    return (stack.top == stack.capacity - 1);
}
 
// Stack is empty when top is equal to -1
boolean isEmpty(Stack stack)
{
    return (stack.top == -1);
}
 
// Function to add an item to stack.It
// increases top by 1
void push(Stack stack, int item)
{
    if (isFull(stack))
        return;
         
    stack.array[++stack.top] = item;
}
 
// Function to remove an item from stack.It
// decreases top by 1
int pop(Stack stack)
{
    if (isEmpty(stack))
        return Integer.MIN_VALUE;
         
    return stack.array[stack.top--];
}
 
// Function to implement legal movement between
// two poles
void moveDisksBetweenTwoPoles(Stack src, Stack dest,
                              char s, char d)
{
    int pole1TopDisk = pop(src);
    int pole2TopDisk = pop(dest);
 
    // When pole 1 is empty
    if (pole1TopDisk == Integer.MIN_VALUE)
    {
        push(src, pole2TopDisk);
        moveDisk(d, s, pole2TopDisk);
    }
     
    // When pole2 pole is empty
    else if (pole2TopDisk == Integer.MIN_VALUE)
    {
        push(dest, pole1TopDisk);
        moveDisk(s, d, pole1TopDisk);
    }
     
    // When top disk of pole1 > top disk of pole2
    else if (pole1TopDisk > pole2TopDisk)
    {
        push(src, pole1TopDisk);
        push(src, pole2TopDisk);
        moveDisk(d, s, pole2TopDisk);
    }
    // When top disk of pole1 < top disk of pole2
    else
    {
        push(dest, pole2TopDisk);
        push(dest, pole1TopDisk);
        moveDisk(s, d, pole1TopDisk);
    }
}
 
// Function to show the movement of disks
void moveDisk(char fromPeg, char toPeg, int disk)
{
    System.out.println("Move the disk " + disk +
                            " from " + fromPeg +
                              " to " + toPeg);
}
 
// Function to implement TOH puzzle
void tohIterative(int num_of_disks, Stack
                  src, Stack aux, Stack dest)
{
    int i, total_num_of_moves;
    char s = 'S', d = 'D', a = 'A';
  
    // If number of disks is even, then
    // interchange destination pole and
    // auxiliary pole
    if (num_of_disks % 2 == 0)
    {
        char temp = d;
        d = a;
        a  = temp;
    }
    total_num_of_moves = (int)(Math.pow(
                         2, num_of_disks) - 1);
  
    // Larger disks will be pushed first
    for(i = num_of_disks; i >= 1; i--)
        push(src, i);
  
    for(i = 1; i <= total_num_of_moves; i++)
    {
        if (i % 3 == 1)
          moveDisksBetweenTwoPoles(src, dest, s, d);
  
        else if (i % 3 == 2)
          moveDisksBetweenTwoPoles(src, aux, s, a);
  
        else if (i % 3 == 0)
          moveDisksBetweenTwoPoles(aux, dest, a, d);
    }
}
 
// Driver code
public static void main(String[] args)
{
     
    // Input: number of disks
    int num_of_disks = 3;
     
    TOH ob = new TOH();
    Stack src, dest, aux;
     
    // Create three stacks of size 'num_of_disks'
    // to hold the disks
    src = ob.createStack(num_of_disks);
    dest = ob.createStack(num_of_disks);
    aux = ob.createStack(num_of_disks);
     
    ob.tohIterative(num_of_disks, src, aux, dest);
}
}
 
// This code is contributed by Sumit Ghosh


Python3




# Python3 program for iterative Tower of Hanoi
import sys
 
# A structure to represent a stack
class Stack:
    # Constructor to set the data of
    # the newly created tree node
    def __init__(self, capacity):
        self.capacity = capacity
        self.top = -1
        self.array = [0]*capacity
 
# function to create a stack of given capacity.
def createStack(capacity):
    stack = Stack(capacity)
    return stack
  
# Stack is full when top is equal to the last index
def isFull(stack):
    return (stack.top == (stack.capacity - 1))
   
# Stack is empty when top is equal to -1
def isEmpty(stack):
    return (stack.top == -1)
   
# Function to add an item to stack.
# It increases top by 1
def push(stack, item):
    if(isFull(stack)):
        return
    stack.top+=1
    stack.array[stack.top] = item
   
# Function to remove an item from stack.
# It decreases top by 1
def Pop(stack):
    if(isEmpty(stack)):
        return -sys.maxsize
    Top = stack.top
    stack.top-=1
    return stack.array[Top]
   
# Function to implement legal
# movement between two poles
def moveDisksBetweenTwoPoles(src, dest, s, d):
    pole1TopDisk = Pop(src)
    pole2TopDisk = Pop(dest)
 
    # When pole 1 is empty
    if (pole1TopDisk == -sys.maxsize):
        push(src, pole2TopDisk)
        moveDisk(d, s, pole2TopDisk)
       
    # When pole2 pole is empty
    else if (pole2TopDisk == -sys.maxsize):
        push(dest, pole1TopDisk)
        moveDisk(s, d, pole1TopDisk)
       
    # When top disk of pole1 > top disk of pole2
    else if (pole1TopDisk > pole2TopDisk):
        push(src, pole1TopDisk)
        push(src, pole2TopDisk)
        moveDisk(d, s, pole2TopDisk)
       
    # When top disk of pole1 < top disk of pole2
    else:
        push(dest, pole2TopDisk)
        push(dest, pole1TopDisk)
        moveDisk(s, d, pole1TopDisk)
   
# Function to show the movement of disks
def moveDisk(fromPeg, toPeg, disk):
    print("Move the disk", disk, "from '", fromPeg, "' to '", toPeg, "'")
   
# Function to implement TOH puzzle
def tohIterative(num_of_disks, src, aux, dest):
    s, d, a = 'S', 'D', 'A'
   
    # If number of disks is even, then interchange
    # destination pole and auxiliary pole
    if (num_of_disks % 2 == 0):
        temp = d
        d = a
        a = temp
    total_num_of_moves = int(pow(2, num_of_disks) - 1)
   
    # Larger disks will be pushed first
    for i in range(num_of_disks, 0, -1):
        push(src, i)
   
    for i in range(1, total_num_of_moves + 1):
        if (i % 3 == 1):
            moveDisksBetweenTwoPoles(src, dest, s, d)
   
        else if (i % 3 == 2):
            moveDisksBetweenTwoPoles(src, aux, s, a)
   
        else if (i % 3 == 0):
            moveDisksBetweenTwoPoles(aux, dest, a, d)
 
# Input: number of disks
num_of_disks = 3
 
# Create three stacks of size 'num_of_disks'
# to hold the disks
src = createStack(num_of_disks)
dest = createStack(num_of_disks)
aux = createStack(num_of_disks)
 
tohIterative(num_of_disks, src, aux, dest)
 
# This code is contributed by divyeshrabadiya07.


C#




// C# program for iterative
// Tower of Hanoi
using System;
 
class GFG
{
    // A structure to represent a stack
    public class Stack
    {
        public int capacity;
        public int top;
        public int []array;
    }
     
    // function to create a stack of given capacity.
    Stack createStack(int capacity)
    {
        Stack stack = new Stack();
        stack.capacity = capacity;
        stack.top = -1;
        stack.array = new int[capacity];
        return stack;
    }
     
    // Stack is full when top is equal to the last index
    Boolean isFull(Stack stack)
    {
        return (stack.top == stack.capacity - 1);
    }
     
    // Stack is empty when top is equal to -1
    Boolean isEmpty(Stack stack)
    {
        return (stack.top == -1);
    }
     
    // Function to add an item to stack.
    // It increases top by 1
    void push(Stack stack,int item)
    {
        if(isFull(stack))
            return;
        stack.array[++stack.top] = item;
    }
     
    // Function to remove an item from stack. 
    // It decreases top by 1
    int pop(Stack stack)
    {
        if(isEmpty(stack))
            return int.MinValue;
        return stack.array[stack.top--];
    }
     
    // Function to implement legal 
    // movement between two poles
    void moveDisksBetweenTwoPoles(Stack src, Stack dest,
                                            char s, char d)
    {
        int pole1TopDisk = pop(src);
        int pole2TopDisk = pop(dest);
 
        // When pole 1 is empty
        if (pole1TopDisk == int.MinValue)
        {
            push(src, pole2TopDisk);
            moveDisk(d, s, pole2TopDisk);
        }
         
        // When pole2 pole is empty
        else if (pole2TopDisk == int.MinValue)
        {
            push(dest, pole1TopDisk);
            moveDisk(s, d, pole1TopDisk);
        }
         
        // When top disk of pole1 > top disk of pole2
        else if (pole1TopDisk > pole2TopDisk)
        {
            push(src, pole1TopDisk);
            push(src, pole2TopDisk);
            moveDisk(d, s, pole2TopDisk);
        }
         
        // When top disk of pole1 < top disk of pole2
        else
        {
            push(dest, pole2TopDisk);
            push(dest, pole1TopDisk);
            moveDisk(s, d, pole1TopDisk);
        }
    }
     
    // Function to show the movement of disks
    void moveDisk(char fromPeg, char toPeg, int disk)
    {
        Console.WriteLine("Move the disk "+disk +
                        " from "+fromPeg+" to "+toPeg);
    }
     
    // Function to implement TOH puzzle
    void tohIterative(int num_of_disks, Stack
                src, Stack aux, Stack dest)
    {
        int i, total_num_of_moves;
        char s = 'S', d = 'D', a = 'A';
     
        // If number of disks is even, then interchange
        // destination pole and auxiliary pole
        if (num_of_disks % 2 == 0)
        {
            char temp = d;
            d = a;
            a = temp;
        }
        total_num_of_moves = (int) (Math.Pow(2, num_of_disks) - 1);
     
        // Larger disks will be pushed first
        for (i = num_of_disks; i >= 1; i--)
            push(src, i);
     
        for (i = 1; i <= total_num_of_moves; i++)
        {
            if (i % 3 == 1)
            moveDisksBetweenTwoPoles(src, dest, s, d);
     
            else if (i % 3 == 2)
            moveDisksBetweenTwoPoles(src, aux, s, a);
     
            else if (i % 3 == 0)
            moveDisksBetweenTwoPoles(aux, dest, a, d);
        }
    }
     
    // Driver code
    public static void Main(String []args)
    {
         
        // Input: number of disks
        int num_of_disks = 3;
         
        GFG ob = new GFG();
        Stack src, dest, aux;
         
        // Create three stacks of size 'num_of_disks'
        // to hold the disks
        src = ob.createStack(num_of_disks);
        dest = ob.createStack(num_of_disks);
        aux = ob.createStack(num_of_disks);
         
        ob.tohIterative(num_of_disks, src, aux, dest);
    }
}
 
// This code is Contributed by Arnab Kundu


Javascript




<script>
    // Javascript program for iterative Tower of Hanoi
     
    // A structure to represent a stack
    class Stack
    {
        constructor(capacity) {
            this.capacity = capacity;
            this.top = -1;
            this.array = new Array(capacity);
        }
    }
     
    // function to create a stack of given capacity.
    function createStack(capacity)
    {
        let stack = new Stack(capacity);
        return stack;
    }
     
    // Stack is full when top is equal to the last index
    function isFull(stack)
    {
        return (stack.top == (stack.capacity - 1));
    }
      
    // Stack is empty when top is equal to -1
    function isEmpty(stack)
    {
        return (stack.top == -1);
    }
      
    // Function to add an item to stack.
    // It increases top by 1
    function push(stack, item)
    {
        if(isFull(stack))
            return;
        stack.array[++stack.top] = item;
    }
      
    // Function to remove an item from stack.
    // It decreases top by 1
    function pop(stack)
    {
        if(isEmpty(stack))
            return Number.MIN_VALUE;
        return stack.array[stack.top--];
    }
      
    // Function to implement legal
    // movement between two poles
    function moveDisksBetweenTwoPoles(src, dest, s, d)
    {
        let pole1TopDisk = pop(src);
        let pole2TopDisk = pop(dest);
  
        // When pole 1 is empty
        if (pole1TopDisk == Number.MIN_VALUE)
        {
            push(src, pole2TopDisk);
            moveDisk(d, s, pole2TopDisk);
        }
          
        // When pole2 pole is empty
        else if (pole2TopDisk == Number.MIN_VALUE)
        {
            push(dest, pole1TopDisk);
            moveDisk(s, d, pole1TopDisk);
        }
          
        // When top disk of pole1 > top disk of pole2
        else if (pole1TopDisk > pole2TopDisk)
        {
            push(src, pole1TopDisk);
            push(src, pole2TopDisk);
            moveDisk(d, s, pole2TopDisk);
        }
          
        // When top disk of pole1 < top disk of pole2
        else
        {
            push(dest, pole2TopDisk);
            push(dest, pole1TopDisk);
            moveDisk(s, d, pole1TopDisk);
        }
    }
      
    // Function to show the movement of disks
    function moveDisk(fromPeg, toPeg, disk)
    {
        document.write("Move the disk "+disk +
                        " from '"+fromPeg+"' to '"+toPeg + "'</br>");
    }
      
    // Function to implement TOH puzzle
    function tohIterative(num_of_disks, src, aux, dest)
    {
        let i, total_num_of_moves;
        let s = 'S', d = 'D', a = 'A';
      
        // If number of disks is even, then interchange
        // destination pole and auxiliary pole
        if (num_of_disks % 2 == 0)
        {
            let temp = d;
            d = a;
            a = temp;
        }
        total_num_of_moves = parseInt(Math.pow(2, num_of_disks) - 1, 10);
      
        // Larger disks will be pushed first
        for (i = num_of_disks; i >= 1; i--)
            push(src, i);
      
        for (i = 1; i <= total_num_of_moves; i++)
        {
            if (i % 3 == 1)
                moveDisksBetweenTwoPoles(src, dest, s, d);
      
            else if (i % 3 == 2)
                moveDisksBetweenTwoPoles(src, aux, s, a);
      
            else if (i % 3 == 0)
                moveDisksBetweenTwoPoles(aux, dest, a, d);
        }
    }
     
    // Input: number of disks
    let num_of_disks = 3;
 
    let src, dest, aux;
 
    // Create three stacks of size 'num_of_disks'
    // to hold the disks
    src = createStack(num_of_disks);
    dest = createStack(num_of_disks);
    aux = createStack(num_of_disks);
 
    tohIterative(num_of_disks, src, aux, dest);
     
    // This code is contributed by decode2207
</script>


Output

Tower of Hanoi for 3 disks:
Move disk 1 from rod S to rod D
Move disk 2 from rod S to rod A
Move disk 1 from rod D to rod A
Move disk 3 from rod S to rod D
Move disk 1 from rod A to rod S
Move disk 2 from rod A to rod D
Move disk 1 from rod S to rod D

Time Complexity: O(2n) Since the iterative solution needs to generate and process all possible combinations of moves for n disks, the number of iterations grows exponentially with the number of disks.
Auxiliary Space: O(n)

Related Articles 

References: 
http://en.wikipedia.org/wiki/Tower_of_Hanoi#Iterative_solution


 



Previous Article
Next Article

Similar Reads

Time Complexity Analysis | Tower Of Hanoi (Recursion)
Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: 1) Only one disk can be moved at a time. 2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk ca
2 min read
Cost Based Tower of Hanoi
The standard Tower of Hanoi problem is explained here . In the standard problem, all the disc transactions are considered identical. Given a 3x3 matrix costs[][] containing the costs of transfer of disc between the rods where costs[i][j] stores the cost of transferring a disc from rod i to rod j. Cost of transfer between the same rod is 0. Hence th
10 min read
Twisted Tower of Hanoi Problem
The basic version of the Tower of Hanoi can be found here. It is a twisted Tower of Hanoi problem. In which, all rules are the same with an addition of a rule: You can not move any disk directly from the first rod to last rod i.e., If you want to move a disk from the first rod to the last rod then you have to move the first rod to the middle rod fi
7 min read
Tower of Hanoi | Set 2
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 = 3Output:Move the 1 disk to next circular right rodMove the 2 disk to next circular right rodMove the 1 disk to next circular right rodMove the 3 disk to next circular ri
12 min read
Recursive Tower of Hanoi using 4 pegs / rods
Tower of Hanoi is a mathematical puzzle. Traditionally, It consists of three poles and a number of disks of different sizes which can slide onto any poles. The puzzle starts with the disk in a neat stack in ascending order of size in one pole, the smallest at the top thus making a conical shape. The objective of the puzzle is to move all the disks
8 min read
Program for Tower of Hanoi Algorithm
Tower of Hanoi is a mathematical puzzle where we have three rods (A, B, and C) and N disks. Initially, all the disks are stacked in decreasing value of diameter i.e., the smallest disk is placed on the top and they are on rod A. The objective of the puzzle is to move the entire stack to another rod (here considered C), obeying the following simple
6 min read
Iterative Deepening Search(IDS) or Iterative Deepening Depth First Search(IDDFS)
There are two common ways to traverse a graph, BFS and DFS. Considering a Tree (or Graph) of huge height and width, both BFS and DFS are not very efficient due to following reasons. DFS first traverses nodes going through one adjacent of root, then next adjacent. The problem with this approach is, if there is a node close to root, but not in first
10 min read
Maximize height of tower using elements from one of the given Subarrays
Given an array arr[] of length N, two arrays start[] and end[] of size M each where {start[i], end[i]} denotes a subarray of arr[] and an integer base, the task is to determine the maximum height of a tower with given base that can be formed using elements from a single subarray bounded by any {start[i], end[i]} and satisfying the following conditi
10 min read
Minimum number of towers required such that every house is in the range of at least one tower
Given a map of the city and the network range, the task is to determine the minimum number of the tower so that every house is within range of at least one tower. Each tower must be installed on top of an existing house. Examples: Input: range : 1 house : 1 2 3 4 5 Output: 2 Input: range : 2 house : 7 2 4 6 5 9 12 11 Output: 3 All cities can be cov
7 min read
Check if the tower of sight issue occurs or not
Given four co-ordinates A, B, C and D where towers need to be constructed, the task is to check if the tower of sight issue occurs or not. Tower of sight issue occurs if the towers at A or C lies in the line joining B and D or vice versa. Examples: Input: A = (0, 0), B = (0, -2), C = (2, 0), D = (0, 2) Output: Yes Explanation: Tower A lies in the l
10 min read
Article Tags :
Practice Tags :