PermMissingElem

Solution:

This java solution to codility problem PermMissingElem scored a 100%

Logic: Iterate over the array and add the elements to a set on which you can do a contains operation. Iterate over the hashset for the first n+1 numbers and if when a specific number is not found in the hashset then that is the missing element.

import java.util.HashSet;
import java.util.Set;
class PermMissingElement{
    public int solution(int[] A) {
        int n = A.length + 1;
        int missingNumber = 0;
        Set<Integer> values = new HashSet<>();
        for (int i=0; i<A.length; i++) {
            values.add(A[i]);
        }
        for (int i=1; i<=n; i++) {
            if (!values.contains(i)) {
                missingNumber = i;
            }
        }
        return missingNumber;
    }
}

Solution 2:

This java solution scored 80% as it failed with larger length (~100,000)

Logic: Calculate the sum of the first n+1 natural numbers. Then iterate over the array and deduct the value from the sum. Whats left of the sum is the missing number. But aha fails with bigger ranges..

    
class PermMissingElement{
   public int solution1(int[] A) {

        int n = A.length + 1;
        long sumOfFirstN = n * (n+1)/2;
        for (int i=0; i<A.length; i++) {
            sumOfFirstN = sumOfFirstN - A[i];
        }
        return (int)(sumOfFirstN);
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s