Solution to Nailing-Planks by codility

8 Apr

Question: https://codility.com/demo/take-sample-test/nailing_planks

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 thoughts on “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:

Leave a Reply

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