#include <iostream>
#include <cmath>
using namespace std;
// Function to find the position of the lowest set bit
int getLowestSetBit(int num) {
int position = 1;
while ((num & 1) == 0) {
num >>= 1;
position++;
}
return position;
}
void towerOfHanoiIterativeBinary(int n, char src, char aux, char dest) {
int totalMoves = (1 << n) - 1; // 2^n - 1
char pegs[3];
if (n % 2 == 0) {
pegs[0] = src;
pegs[1] = dest;
pegs[2] = aux;
} else {
pegs[0] = src;
pegs[1] = aux;
pegs[2] = dest;
}
for (int moveNum = 1; moveNum <= totalMoves; ++moveNum) {
int disk = getLowestSetBit(moveNum); // which disk to move
// Calculate source and destination pegs
int from = ( (moveNum >> (disk - 1)) & 3 ) % 3;
int to = (from + 1 + (n % 2 == 0 ? 2 : 1)) % 3;
cout << "Move disk " << disk << " from " << pegs[from] << " to " << pegs[to] << endl;
}
}
int main() {
int n = 5; // Number of disks
towerOfHanoiIterativeBinary(n, 'A', 'B', 'C');
return 0;
}
