PermMissingElem- find the missing element in a given permutation in C# I just encountered this question in codility but apparently this question has been asked in java already  (here, here).

Task description

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.
  


My approach is shown below:

  public static int permMissingElement(int [] elements)
            {
                if (elements.Length == 0)
                {
                return 0;
            }

            else if (elements.Length == 1)
            {
                return elements.First();
            }
            else
            {
                Array.Sort(elements);
                List&lt;int&gt; listOfElementsInTheArray = elements.ToList&lt;int&gt;();
                IEnumerable&lt;int&gt; missingNumber = Enumerable.Range(listOfElementsInTheArray.First(), listOfElementsInTheArray.Count).Except(listOfElementsInTheArray);

               return missingNumber.Count() == 0 ? 0 : missingNumber.First();

            }
        }

 static void Main(string[] args)
        {
            Console.WriteLine(permMissingElement(new int [] {2,3,1,5}));
            Console.ReadLine();
        }


Explanation: My approach was to display 0 if the array doesn't contain an element and return the element if it contains 1 . In addition, if the array contains 2 or more elements, it is sorted and converted to a list. Once its a list , i generate a complete sequence of the same list and remove any list that exists in the previous. I return the missing number afterwards . But surprising codility grades me in terms of correctness 20% and performance 80% and in general 50%. I know this can be better improved, any suggestions would be appreciated.
It is possible to solve the problem without sorting the array (which is expensive). The input array is actually a simple arithmetic sequence 1, 2, 3, 4 ... N+1, the numbers are just in a jumbled up order and one of them is missing.

The sum of the sequence is easy to calculate as n/2(1+n) (here n = N + 1). The sum of the input array will be the same as this, minus the value of the missing element. So the value of the missing element is the difference between the sum of the entire sequence and the sum of the input array.

    public static int permMissingElement(int[] elements)
    {
        int n = elements.Length + 1;
        int sumOfAllElements = (n * (1 + n)) / 2;
        int missingElement = sumOfAllElements - elements.Sum();
        return missingElement;
    }




Edit:

The maximum value of N is 100,000, which would cause an arithmetic overflow when calculating the sum of the sequence. The straightforward solution is to use longs for the calculations instead:

    public static int permMissingElement(int[] elements)
    {
        long n = elements.Length + 1;
        var sumOfAllElements = (n * (1 + n)) / 2;
        var missingElement = sumOfAllElements - elements.Select(x =&gt; (long)x).Sum();
        return (int)missingElement;
    }