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

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.


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:


Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: