PROBLEM LINK:
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Brute Force , BFS.
EXPLANATION:
The constraints make the problem to be solved by a Brute Force approach. (8!=40320) BFS can be used here to find the minimum number of moves to make the array sorted. BFS is applied to a tree with array in their nodes and each node with N-k children.
The root of the tree is the given permutation. Push N-k children in the stack where ith child of the node is a reverse of (i to i+k) elements of the current array. Hence, the parent and each child differ by one move.If parent has D moves then each child can be obtained by D+1 moves.In BFS after popping the node (array) each time check if its sorted. IF its sorted then the number of moves associated with the node is the answer to the problem.