Saturday, December 30, 2006

Reverse an Array

An array of size N has distinct values 1…N in random order. You have only operator called rev(X) (where X is any value from 0 to N-1) which reverses all values from 0 to X (example values 2,3,1,4 and rev(2) gets you 1,3,2,4). Our objective is to sort the array using minimum number of Rev(X) functions. How many permutations of N size array require exactly N number of rev(X) operators to get sorted?

My answer is,
1) find out max num. in an array say position i, use rev(i) and after use rev(N).
2) repeat above step by decreasing N by one each time

No comments:

Post a Comment