Interesting puzzle. It is not an easy problem. But the experience of getting stuck trying to solve the problem is in itself rewarding.

**Hint:**Try and specialize. Organize the results of specialising. Make a conjecture, however wild. Check and prove your conjecture.

**Followup**: Given by Giridhar on his blog. Using this, find an O(1) space algorithm to "rotation of array" problem where you are asked to rotate the array by a given amount k. For example, rotating Array containing 3, 5, 9, 14, 1, 2, 11 by 3 positions will yield 14, 1, 2, 11, 3, 5, 9.

O(k) space algorithm is of course trivial. Can you find an O(1) space algorithm?

ab/lcm

ReplyDeletecreate ring with extra slot. shift 1 by 1 till u get there.

ReplyDelete:-/

ReplyDeletey = # of pins

ReplyDeletex = gap

#of threads = gcd (y,x)

break the cirlce into an infinite line

now keep up with the procedure

if gcd != 1, then some positions will never be visited, positions visited would be multiples of gcd (y,x)

hence the result.

Below Proof is in the same spirit as of 'drunksaint'.

ReplyDeleteObservtions :

1)All cycles are disjoint

2)All cycles are of same size ( by symmetry ).

Let,

N be number of Pins, numbered 0 ..(N-1)

G be the Gap

C be number of Cycles.

and S be size of each cycle.

From above observations, it follows that

N = C * S -- (1)

Now let us concentrate on the cycle that begin and end with Pin 0.

As we move in steps of G, S shud be SMALLEST integer obeying following equation :

(S * G )% N = 0

This implies that S * G = LCM( N, G ) --(2)

From (1) and (2) it follows that C =(N * G)/LCM( N,G ) = GCD( N,G ).

For the follow up thing,

Pins corresponds to array elemets,

Gap corresponds to shift K ( amount by which we need to rotate array )

Hence, as we know the number of cycles which arise , and elements which belong to a given cycle, array can be rotated using N + GCD(N,K) Assignment operations.

Just for sake of completeness, let me mention that there is another relatively inefficient O(1) solution for rotation problem ::

let array be A#B where A is of size K and B of size ( N - K ).

if we rotate whole array ( using SWAP operations )we get B^R#A^R ( concatenation of B reversed with A reversed )

Now we rotate parts individually, this gives us (B^R)^R#(A^R)^R = BA, as desired.

In this solution we are doing N SWAPS , whereas first solution requires just N + GCD(N,K) ASSIGNMENTS .

@Suarabh.. Thanx for the answer.. Interesting point raised in your second comment.. I was confused.. @Giridhar Thanx for the proof and the awesome explanation @Pandeyji.. Nice solution..

ReplyDelete