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

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

  3. I used different approach:

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

  5. 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. My 100% C++ version:

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!