# Solution to Nailing-Planks by codility

8 Apr

Question Name: Nailing Planks or NailingPlanks

This question is designed to be solved with binary search method (BUT there is a better solution! It is updated at the end of this post.). And the binary solution is as following:

In addition, there is an alternative solution without binary algorithm. This solution has a different but similar time complexity and space complexity (O(M+N)). And it does pass all the tests. Actually, for all binary search algorithms, they have a common issue: they access the items in different and non-consecutive places, that makes the modern data cache system valueless and helpless. That is the battle between heap sort and merge sort. That is also the battle among binary algorithms and their non-binary competitors. At lease in this war, non-binary wins. In the test result, the non-binary algorithm costs noticeable less time.

Finally, thanks to @Guillermo (StackOverflow Profile) again, here is the C++ solution.

UPDATE (May 2nd, 2016): Many thanks toÂ Dragan@ (blog): he proposed a wonderful solution with linear time complexity. HisÂ blog includesÂ a Java solution. And here is my Python.

### 11 Replies to “Solution to Nailing-Planks by codility”

1. Juraj says:

While codility will give you 100% for these solutions, they exceed specified time complexity. Worst case – they are O(m*n). Below is a test sample to demonstrate this. It has the same number of planks and nails (n) and clearly shows that if you double the input, the total runtime time is quadrupled.

• Sheng says:

Yes, in the first solution:
Linear search all the quanlified nails.

So in the worst-case, it is N*M.

2. Vishnu Valleru says:

# This solution in python, takes O((N+M)*log(M) * log(log(M))), but passes the test suite on codility

• Sheng says:

Thanks for sharing!

I used different approach:

• Sheng says:

Thanks for sharing!

• Shashi says:

Can you please explain the logic of your code? What is the purpose of nailsCounter?

• Sheng says:

Thanks for sharing a different solution!

4. Dragan Bozanovic says:

I managed to find a solution with linear complexity. In my solution I first discard all planks that completely wrap other planks, because a nail used for a wrapped plank can be used for all planks that wrap it.

• Sheng says:

Great idea!!! Many thanks!