Threaded Pins

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.

Advertisements

4 Responses to “Threaded Pins”

  1. Pratik Poddar Says:

    For n pins and gap of m,
    Is the answer gcd(n,m)?

  2. connect2ppl Says:

    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 ?

  3. Pratik Poddar Says:

    🙂 .. 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 🙂

  4. Pratik Poddar Says:

    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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: