O(N*log(log(N))) algorithm for Codility's Peaks?

Question

The task description is here: https://codility.com/demo/take-sample-test/peaks It's also here: Codility Peaks Complexity

First, I tried solving this myself but was only able to come up with what I believed to be a brute force solution. However, it scored 100/100: https://codility.com/demo/results/demoRNWC3P-X4U

Which obviously is completely unsatisfying for me. ;) The outer loop is called for each factor of N (or for each peak, whichever is smaller) and the inner one is called for each peak (just checking if there's a peak in every block). Maybe that's O(N^2), maybe a bit better (since it passes the tests in time limits) but I'm almost sure it's not O(N*log(log(N))).

Then I tried searching for an O(N*log(log(N))) solution but everyone else seems to have a pretty similar solution to mine.

So does anyone have an idea for an O(N*log(log(N))) (or a better one) solution?

Also, if anyone could tell me what complexity my solution has I'd be grateful.

Wow

I can't see the problem without logging in. Can you reproduce the problem description in the question itself? – Clyte

Afaik, it's copyrighted so it shouldn't be copied here? However, one user has already done it and I added a link to his question (with the task description). – Wow

Answer 1

Your code is O(n d(n)) where d(n) is the number of divisors of n. On [1, 100000], d(n) is maximised at 83160 = 2^3 3^3 5 7 11, which has 126 divisors. According to Wikipedia, d(n) is o(n^epsilon) for every epsilon>0, so it grows rather slowly.

To get an O(n log log n) solution, build a partial sum array telling you how many peaks are left of each point. Then you can tell whether there's a peak in an interval in O(1) time. Checking a divisor d then takes O(n/d) time. Adding up n/d over all divisors d is the same as adding up d over all divisors d, and the result is, according to the same Wikipedia page, O(n log log n).

Headfirst

I understood all except the last part. What do you mean "Adding up n/d over all divisors d is the same as adding up d over all divisors d"? – Wow

@NPS: There's an involution on the set of divisors of n given by i(d) = n/d. (An involution is a bijection from a set to itself that, when applied twice, does nothing.) So sum(d divides n) n/d = sum(d divides n) n/i(d) = sum(d divides n) d. – Headfirst

Answer 2

I've implemented a solution in the style suggested by tmyklebu (thanks!) which should be n.log(log(n)). Codility no longer test 'performance' on this problem (!) but the python solution scores 100% for accuracy.

In passing, if you've been doing the Codility Lessons you'll remember from the Lesson 8: Prime and composite numbers that the sum of harmonic number operations will give O(log(n)) complexity. We've got a reduced set, because we're only looking at factor denominators. Lesson 9: Sieve of Eratosthenes shows how the sum of reciprocals of primes is O(log(log(n))) and claims that 'the proof is non-trivial'. The sum of divisor reciprocals is different to the sum of prime reciprocals but I'd suggest that it falls into the 'non-trivial' proof category too!

def solution(data):

    length = len(data)

    # array ends can't be peaks, len < 3 must return 0    
    if len < 3:
        return 0

    peaks = [0] * length

    # compute a list of 'peaks to the left' in O(n) time
    for index in range(2, length):
        peaks[index] = peaks[index - 1]

        # check if there was a peak to the left, add it to the count
        if data[index - 1] > data[index - 2] and data[index - 1] > data[index]:
            peaks[index] += 1

    # candidate is the block size we're going to test
    for candidate in range(3, length + 1):

        # skip if not a factor
        if length % candidate != 0:
            continue

        # test at each point n / block
        valid = True
        index = candidate
        while index != length:

            # if no peak in this block, break
            if peaks[index] == peaks[index - candidate]:
                valid = False
                break

            index += candidate

        # one additional check since peaks[length] is outside of array    
        if index == length and peaks[index - 1] == peaks[index - candidate]:
            valid = False

        if valid:
            return length / candidate

    return 0

Samal

How did you conclude that this if condition means there is no peak? if peaks[index] == peaks[index - candidate]: valid = False break – Unkindly

Also, can you please explain this second if condition as well? if index == length and peaks[index - 1] == peaks[index - candidate]: valid = False – Unkindly

In answer to your first question: look at what 'peaks' contains. It's a cumulative count of how many peaks have been found so far (to the left of the current index). If you compare two points in the array and they have the same values, then no new peak was found. – Samal

In answer to your second question, the end of the array (what should be the last iteration of the 'while' loop is special. The rules state that the end of the data array cannot be considered a peak. Given how we have set this up, peaks[length] would be out of the array, so we need to look at peaks[length-1] instead. – Samal

To get a better handle on what's going on, you could try a small array and work this through on paper. Or look at @rafalio's example, and pick a few key points: https://mcmap.net/q/945378/-codility-peaks-complexity – Samal