Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I can not figure out why I didn't get 100% success from the Codility's Perm-Missing-Element test even I solve with \$O(n)\$. I will appreciate any advice/answers.

You can see the problem, my code, and the scores on the Codility site, as well as here.

Problem Definition

A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.
Your goal is to find that missing element.
Write a function:

class Solution { public int solution(int[] A); }  

that, given a zero-indexed array A, returns the value of the missing element.
For example, given array A such that:

A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5

the function should return 4, as it is the missing element.
Assume that:
N is an integer within the range [0..100,000];
the elements of A are all distinct;
each element of array A is an integer within the range [1..(N + 1)].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

Solution

Here is the code I wrote as an answer.

public class Solution {

        public int solution(int[] A) {

            int N = A.length + 1;
            int total = N * (N + 1) / 2;

            for (int i : A) {

                total -= i;
            }

            return total;
        }
    }
share|improve this question
    
Doesn't codility provide you more details about this ? Type of test cases for instance –  Josay Apr 17 at 13:19
    
I shared a link which just give a brief test report. They don't share a detailed report. –  quartaela Apr 17 at 13:23
    
Ha ok, I didn't see that. So this is actually a problem of correctness and not of performance. –  Josay Apr 17 at 13:44

3 Answers 3

up vote 11 down vote accepted

@chillworld is correct in his observation that the issue is related to the int overflow causing the problems in the performance tests.

The more accurate solution to this is to use a long to set the score, instead of an int.

public class Solution {

    public int solution(int[] A) {

        long N = A.length + 1;
        long total = N * (N + 1) / 2;

        for (int i : A) {

            total -= i;
        }

        return (int)total;
    }
}

As for your code, I understand why you have variables with names like N and A, because those are the variable names used in the problem.

Those variable names do not conform to standard Java naming conventions though. They should be meaningful names, and start with a lower-case letter, like sum, and data.

the fact that my code below still uses N is not an indication that it is OK .... Do what I say, not what I do...


Update

Sometimes, the performance tricks in Java can be a PITA.

  • Whenever you can, declare your variables as final
  • declare your methods as final
  • declare variables and for-loop variables as final (if you use the enhanced-for semantics).
  • addition may, or may not be faster than subtraction.

Using this code:

class Solution {

    public final int solution(final int[] data) {

        final long N = data.length + 1;
        final long total = (N * (N + 1)) / 2;

        long sum = 0L;

        for (final int i : data) {

            sum += i;
        }

        return (int)(total - sum);
    }
}

Scores 100%


Update 2 final is not the issue:

public int solution(int[] data) {

    long N = data.length + 1;
    long total = (N * (N + 1)) / 2;

    long sum = 0L;

    for (int i : data) {

        sum += i;
    }

    return (int)(total - sum);
}

Also scores 100%

share|improve this answer
    
believe me I tried that solution which gives the same result :). But variable names doesnt affect performance right ? –  quartaela Apr 17 at 13:27
    
@quartaela - updated answer with 100% solution. –  rolfl Apr 17 at 13:37
    
thanks a lot but I dont get it. How defining variables as final boost the performance from 60 to 100? –  quartaela Apr 17 at 13:41
    
@quartaela - I am pretty convinced your code would have passed with just the long-based arithmetic.... the performance tests were failing, they were not slow. The code above just gives a solution that works in all situations, not just smaller datasets. I will put another test through with the same code, but different final, and see what happens. –  rolfl Apr 17 at 13:44
    
Impressive, it does not do much for my opinion of Java though :\ –  konijn Apr 17 at 13:45

From the site :

WRONG ANSWER
got -2147483647 expected 1

So int has overflow because you count everything up. Mine solution to that problem :

public int solution(int[] A) {
    int previous = 0;
    if (A.length != 0) {
        Arrays.sort(A);
        for (int i : A) {
            if (++previous != i) {
                return previous;
            }
        }
    }
    return ++previous;
}

result see here : https://codility.com/demo/results/demoS45RNV-37J/

share|improve this answer
4  
Arrays.sort is typically an O(n log n) operation, so it will likely fail the scalability test. –  rolfl Apr 17 at 13:23
    
Did I miss something in the requirements? When I sent an input of int[] A = {26,23,21,24,22};, I did not get the desired result using your method. It could be that I am missing something in the requirement, so please clarify. –  Kay Ashton Jul 7 at 3:41
    
@KayAshton This won't work cause the pre requirement is that you start at 1 (or 2 if 1 is missing). Also you can't have an exact result when you have int[] A = {25,23,21,24,22}; because it could be 20 or 26. –  chillworld Jul 7 at 10:33

@rolfl

Changing to long will not fully solve the problem. It only delay the overflow.

I 100% agree your solution when the array is small. My solution require more codes and it works with any inputs. The first method is to sort the array but since we know the array will be like array[i] = i+1 based on the pre-condition, the sorting only took O(2n) at the worst case. And the helper method will loop again just to find the missing number which will take another O(n) time at the worst case. The total is O(3n) which meets the time complexity and since we only modify the input array, the space complexity is O(1).

public static int getMissedNumber(int[] numbers) {
    for (int i = 0; i < numbers.length - 1;) {
        if (numbers[i] != i + 1 && numbers[i] != 0) {
            int position = numbers[i] - 1;
            int temp = numbers[position];
            numbers[position] = numbers[i];
            numbers[i] = temp;
        } else {
            ++i;
        }
    }
    return findMissedNumber(numbers);
}

private static int findMissedNumber(int[] numbers) {
    for (int i = 0; i < numbers.length; ++i) {
        if (numbers[i] == 0) {
            return i + 1;
        }
    }
    return -1;
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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