Solution to Peaks by codility

26 Jan

Question: http://codility.com/demo/take-sample-test/peaks

Question Name: Peaks

UPDATE on July 18th 2015: Many thanks to @Antonio Correia (https://codesays.com/2014/solution-to-peaks-by-codility/#comment-11725) !!! @Antonio Correia found a huge bug in my solution, even though it passed the codility.com. The bug has been fixed.

23 thoughts on “Solution to Peaks by codility

  1. Hi Sheng, I’ve found a Java solution to this problem here http://rafal.io/posts/codility-peaks.html
    but I like yours better, you loop until sqrt(lenA) and while storing the index of the peak like it’s done in that solution is interesting, I still prefer your method of memorizing the peaks_until_here[] and checking that number against next block’s number.
    But I quite honestly did not understand your solution completely. It might be because I started learning Python on my own just last month, but starting from
    blocks, block_size = candidate, A_len//candidate
    I have some difficulties to fully grasp what you are doing there (starting from the meaning of the pasted code line, what does it do exactly? I have a hypothesis, but…), could you help me out?

    thank you

    • It is trying and computing every possible partition plan. For a game with length 10, we could divide it into 2 blocks with 5 elements in each, or into 5 blocks with 2 elements in each. That is why we use two tries on each one candidate:
      blocks, block_size = candidate, A_len//candidate
      block_size, blocks = candidate, A_len//candidate

      In terms of how to check whether the partition plan is acceptable or not, you could draw it on paper, and follow each step to simulate the program. That will help you to better understand it.

      • Great solution, I went linear from 3 to length / 2 inclusive and while that may be faster for small cases and still conforms to O(N*log(log N)) your’s sound better. Perhaps, since we are looking for the smallest blockSize, perhaps I’d go further, placing the complements of block size in a list in reverse order and checking them in a new for loop. This way you ensure you parse them by order and don’t need the candidate variable, you can simply return immediately when found. This way you don’t need to parse ALL possible solutions, only until a match is found.

        Cheers

  2. Hey, an alternative python solution.

    I first count the number of peaks, and down from there I try to check if there is a peak in a block. Block sizes obviously must be integral peak_cnt divisors.

    • Thanks for your novel solution!

      PS: I have no idea about the commment system of WP. But it is really unfriendly for code, possibly for security issue.

    • Thank you Martin and Sheng! Two kind of related questions:

      Can anyone please tell what is the time complexity of Martin’s code?

      What would be the maximum number of peaks that an array of size n can have?

      Thanks a lot for your help.

    • Why is this solution O(n*log(logn))?

      In my view, it iterates at most N times (or that many times how many divisors N have) over an array of peaks which can be in the worst case n/2 (every other item is peak). So in math it comes to O(n*n/3) = O(n^2). Unless we can say that number of divisors of N are at most log(logn) which I have never seen.

      • Yes, it is not. However, the “for size in xrange(len(peaks), 0, -1)” could be optimized with binary search to make it O(N*log(N)).

  3. Hello,

    Great site Sheng! Here is my C++ solution. Probably could be optimized a lot, but now I’m focusing on next task 😉

  4. I am having 3 has result for A = [1,2,3,4,5,6,5,5,5,6,5,6] but the first slice does not have any peak.
    The way you’re looking for peaks in the slices does not check if there is one peak on the first slice, but I may be wrong and missing something. Cheers.

  5. Here’s my solution.

  6. My original solution that passed all test cases is almost 60 lines! Then after checking your and all other people’s brilliant solutions, Martin’s is the closest one to mine. I managed to replace the bool array with a variable that marks the result for the division operation against the last peak. It’s trivial though.
    My code is still around 50 lines, partially because of the curly bracket… 🙂

    Could you please help me understand why my solution is NO(log(logN))? I know it’s definitely not O(N^2), but have trouble to round it down.

    Thanks!

    • Sorry, I cannot figure it out~ It seems “for (int k : peaks)” works for O(N) and “if (0 == len % d)” limits the outside while to be O(logN) or O(log(logN)).

      • Thank you for the reply! After reading your solution by keeping peaks position up front, I came out this

  7. Why is Sheng’s solution O(N*log(logN))??
    It looks to me as if it’s O(sqrt(N)*N),

    Because the outer look goes over sqrt(N) possible partition options, (even though not everything is divisible but I don’t know of a tighter bound)
    for each possible partition, you might check a number of partitions that is O(N).
    For example for an even number, when you check the partitions of size 2, you check N/2 paritions.
    And that’s why it seems to me that it’s O(sqrt(N)*N), which is worse than (log(logN))*N).

    I realize I’m wrong somewhere, but can’t see where. Can anyone explain to me please?

  8. Could anyone explain to me why Sheng’s solution is O(N*log(logN)) and not O(N*sqrt(N)) ??
    It seems to me that per each possible division up to sqrt(N), it goes all over all partitions.
    But some paritions could have up to O(N) blocks, so isn’t this O(sqrt(N)*N))??

    Thanks!

Leave a Reply

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