CODILITY.COM - LESSON 1 - PermMissingElement

THE PROBLEM:

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)].

MY SOLUTION ( 100% score, time complexity O(n) or O(n*log(n))) 

class Solution {

    public int solution(int[] A) {

        Array.Sort(A);

        int l = A.Length;

        int missing=l+1;

        if (l == 0) return missing=1;

        for (int i=0; i<l; i++)

        {

            if (A[i] != i+1)

            {

             missing = i+1;

             break;

            }

        }

        return missing;

    }

}

WWW.codility.com

There are two situations: 

• when the array length is = 0 which needs to return 1 as missing element. 
• And when the array length is != 0,then it needs to find the missing element (1, ... N+1).

If the array gets sorted, every present element before the missing element will have an index = the element itself - 1 as indexes start with 0 and the array elements start with 1.

Which brings the condition to check A[i] != i + 1, and if it is, then the missing element should be there (which is i+1). After finding it, break as no need to continue.

PR