2
$\begingroup$

There are numbers from 1 to n, which are inverted such that it results in numbers from n to 1. If only two consecutive numbers are stapled at a time and are inverted, how many moves are required?

$\endgroup$
  • 3
    $\begingroup$ If the posted answers are the intended ones, this is a fair question. However, its wording needs work. "Inverted" indicates "turned", & if $n$ things are inverted, that means each thing is inverted, not that the things' order is changed. And "stapled" needs to be either defined or replaced by a word whose meaning is clear. $\endgroup$ – Rosie F Jun 17 '16 at 8:47
  • $\begingroup$ What about just using the function: $f(x) = n+1-x$ ? $\endgroup$ – Ian MacDonald Jun 17 '16 at 13:57
2
$\begingroup$

In order to overlap any previous numbers you have to swap with it atleast once. Now for every number at pos p you have atleast n-p-1 numbers to be swapped with.

So solution will be

$$\sum_{i=1}^{n-1} i = \frac{n*(n-1)}{2}$$

Example for 5 4 3 2 1

5 needs to be swapped with 4 numbers
4 needs to be swapped with 3 numbers
3 needs to be swapped with 2 numbers
2 needs to be swapped with 1 number.

Thus 1+2+3+4 = 10

$\endgroup$
1
$\begingroup$

from the way you described a move I can say there is two cases :

n is even : then we have to do n/2 moves

n is odd : there is then (n-1)/2 moves.

$\endgroup$
  • 3
    $\begingroup$ Your answer looks like it would be correct, except for the word "consecutive" in the question. $\endgroup$ – Gordon K Jun 17 '16 at 8:17
  • $\begingroup$ yes you're right. It seems I passed over that word too quickly ! $\endgroup$ – Joulin Nicolas Jun 17 '16 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.