Threaded Pins
Suggested to me by Giridhar Addepalli (IITK CSE Alumnus, Yahoo! Sr. Software Engineer). Nice puzzle. Original Source is "Thinking Mathematically" (Amazon Link). Giridhar posts nice mathematical problems on his blog.
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?
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