1
\$\begingroup\$

This is part of a series of algorithmic lessons and tests by Codility.

For copyright reasons, I cannot reproduce the question, which asks to compute the number of distinct absolute values in a given sorted array.

The question requires a response in \$O(n)\$ time complexity. My response (below) was detected as \$O(n*log(n))\$ by Codility, but I have no idea why. It looks to me like we're only going to go over each item of the array once. Am I wrong or is this \$O(n)\$?

public int solution(int[] A) {
    // write your code in Java SE 8
    int result = 0;
    int start = 0;
    int end = A.length - 1;

    while (start <= end) {
        result++;
        int startValue = Math.abs(A[start]);
        int endValue = Math.abs(A[end]);
        int currentValueFound = Math.max(startValue, endValue);
        while (start <= end && Math.abs(A[start]) == currentValueFound) {
            start++;
        }
        while (start <= end && Math.abs(A[end]) == currentValueFound) {
            end--;
        }
    }
    return result;
}

In addition, if anyone has an idea what could have triggered the error in the arth_overflow test, I am interested.

\$\endgroup\$
1

2 Answers 2

2
\$\begingroup\$

I don't see any reason why your solution would not be O(N).

However, it would fail if the array contained Integer.MIN_VALUE, since its absolute value won't fit within an int.

\$\endgroup\$
0
\$\begingroup\$

Your solution is provably \$O(n)\$. With each iteration of any of the inner loops you get rid of one value. Therefore their count is upper bounded by \$n\$.

In every iteration of the outer loop, you make at least one iteration of some inner loop. Therefore the count is bounded by \$n\$, too.


I guess, Codility does some syntactical analysis and sees the nested loops. Try to convert the inner loops into ifs (keep the current maximum value across iterations).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.