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

### 15 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?

• Sam says:

It’s like a prefix sum, with this you can tell if there is a nail between any two position.

• Sheng says:

Thanks for sharing a different solution!

• Sheng says:

Great idea!!! Many thanks!

4. Jack says:

Hello I implemented a similar javascript version of your python binary solution but only get 75% ( 100% correct results but 2 timeouts at the performance tests ).
Could anyone help me to figure out what is wrong with the performance of my code ?
Thank you very much
Cheers
Jack

5. vishnu babu says:

The below solution makes use of a hash lookup & not use binary search.
Passes all codility test cases. Complexity is linear. Instead of binary search it does a hash lookup. The hash contains entry for all points. The value is the first nail (position and point) from that point.

6. Luiz doleron says:

My 100% C++ version:
https://app.codility.com/demo/results/trainingYES68R-VHZ/