Semi-Hanoi is a problem very similar to Hanoi problem. The only difference is that your input in semi-Hanoi must be an even number of disks like 2n and they are set as shown in the following figure-a. The peg A has all the even numbered disks such as 2,4,6, and the peg B has the rest (all the odd numbered disks such as 1,3,5,...). the rules of movement in semi-Hanoi is the same as Hanois rules: only one disk can be moved at a time a bigger disk cannot be placed on top of a smaller one The goal is to move all the disks on the peg C in order as shown in figure-b.

Write an efficient function named semiHanoi(2n, A, B, C) in C++ that prints how to move all 2n disks to the tower C as shown in figure-b. The function must calculate and return the number of movements.

Calculate the time complexity of your function. Show your work.

a-input or starting point b-Goal or output a-input or starting point b-Goal or output