For description of the problem see Threaded Pins

How many pieces of thread will be needed in general ? i.e; given number of pins N and clockwise gap G, Express the number of Threads needed T, as a function of N & G.

Source : ” Thinking Mathematically ” by John Mason et.al

PS: This problem is related to ” rotation of array ” problem where you are asked to rotate the array by a given amount using only O(1) extra space. For example, rotating Array containing 3, 5, 9, 14, 1, 2, 11 by 3 positions will yield 14, 1, 2, 11, 3, 5, 9.

PPS :** **I** **highly recommend ” Thinking Mathematically ” for kids, it helps to develop good practices which aid in solving problems.

### Like this:

Like Loading...

This entry was posted on December 21, 2009 at 2:31 pm and is filed under Puzzle. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

January 4, 2010 at 2:11 pm |

For n pins and gap of m,

Is the answer gcd(n,m)?

January 4, 2010 at 2:26 pm |

Hurrayyyy .. My blog has got its first comment !!

Thanks Pratik .

Yes, GCD ( n , m ) is the right answer.

Did u discover its relation to ” Rotation of Array ” problem ?

January 4, 2010 at 2:34 pm |

🙂 .. Congrats!!

Yes… the relationship is beautiful and subtle..

Find the threads (gcd((n,m) in number).. and shift by one position.. shifting by one position can be done in O(1) So, we can do k-shift in O(1) space 🙂

January 5, 2010 at 10:20 am |

Can you please help by answering to the question in one of the comments here:

http://pratikpoddarcse.blogspot.com/2010/01/threaded-pins.html

Thanx