PermMissingElem- find the missing element in a given permutation in C#

Question

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<int> listOfElementsInTheArray = elements.ToList<int>();
                IEnumerable<int> 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.

Answer 1

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 => (long)x).Sum();
        return (int)missingElement;
    }

Answer 2

You could also solve it without sorting by xor all expected number and afterwards xor all elements from the array - that should be a little bit faster:

public int FindMissing(params int[] values)
{
    if (values.Length == 0) return 0;

    int result = 0;
    for (int i = 1; i <= values.Length + 1; i++)
        result ^= i;
    for (int i = 0; i < values.Length; i++)
        result ^= values[i];
    return result;
}

Answer 3

You could kind of duplicate the array because you know all the desired values then, you could use XOR to find the missing one, using just one for loop should be sufficient:

public int solution(int[] A) {
    // write your code in C# 6.0 with .NET 4.5 (Mono)

    int l =A.Length;
    int result=0;

    for(int i=1; i < l+2 ; i++ ){
        result=result^i;
        if(i-1<l)
            result=result^A[i-1];
    }

    return result;

}

Answer 4

The empty array case seems off. From the problem description, if given an empty array as input, it means that \$N\$ is 0 and the range for values is \$[1..1]\$ thus the missing value is 1.

For the length 1 case, the missing value can never be in the list so returning the first element in the list is incorrect. If \$N\$ is 1, the range is \$[1..2]\$ and the missing value is 1 if the first value is 2, and 2 if the first value is 1.

For theses two special cases I am not sure that I would bother with custom code. It makes the code faster to run in these cases at the cost of making the code more complicated to read and maintain - OK, it is only an exercise and will not be maintained but the general point still applies, unless one is sure that we will have a disproportionate number of empty and 1 element arrays to be processed the custom code is not worth the cost.

I don't know the \$O\$ notation value for sorting the input array, creating the new array and then doing an except on two sorted arrays but it seems to be more complicated (and presumably takes longer) than simply iterating through the sorted array.

public int FindMissing(int[] values)
{
    Array.Sort(values);
    var ret = values.Length+1;

    for (var index = 0; index < values.Length; index++)
    {
        if (values[index] != index+1)
        {
            return index+1;
        }
    }

    return ret;  // handles cases where the last element is missing
                 // including empty array

}

Answer 5

gfv posted the optimal solution, but there is also a lot you can learn from finding out how to improve your code. The most important thing is correctness. As AlanT said, you don't have to write special code for the cases where the array has 0 or 1 elements, and your special code for those cases is incorrect. The code for assigning missingNumber is incorrect as well. The range to check against should always start from 1 and have the count be elements.Count + 1. So you don't need to sort at all. And if you did want to get the minimum value, you can just call Min() instead of sorting and then calling First(). missingNumber should always contain exactly 1 element, so you don't need to check if Count() is equal to 0. If the count is 0, then the input or your code is incorrect. Calling Count() and First() is wasteful because it causes the calculations to populate the IEnumerable to get performed twice. If you have to call two methods that cause an IEnumerable to get enumerated, you're usually better off converting it to a list or array first.

Answer 6

There is a comment in the OP by @EricLippert that reveals how trivial this should be. There is absolutely no need to sort the array, already nicely demonstrated by @gfv. I wrote a little sample in DotNet Core 2.0 that generates a large list, shuffles that list, and then removes the last item. The challenge is to find that missing item.

The answer to the challenge is in the FindMissingNumber method. Everything else is setting up the challenge. You have many fine answers here already. I just wanted to try something with DotNet Core 2.0!

    static void Main(string[] args)
    {
        // Trigger jittr to compile method to omit that time later.
        FindMissingIndex(new int[] { 1, 2, 3 });

        var maximum = 100000;
        var sampleList = GetSampleList(maximum);

        var stopwatch = Stopwatch.StartNew();
        var missing = FindMissingNumber(sampleList);
        stopwatch.Stop();

        Console.WriteLine($"List Ranging from 1 to {maximum:N0}");
        Console.WriteLine($"Missing Value = {missing:N0}");
        Console.WriteLine($"Elapsed {stopwatch.Elapsed.TotalMilliseconds} milliseconds");

        // Sanity check to confirm answer:
        var correct = true;
        foreach (var value in sampleList)
        {
            if (value == missing)
            {
                correct = false;
                break;
            }
        }
        Console.WriteLine($"Sanity Check returns {correct}.");

        Console.WriteLine();
        Console.WriteLine("Press ENTER key to close.");
        Console.ReadLine();
    }

    private static IList<int> GetSampleList(int maximum)
    {
        const int lowerLimit = 3;
        const int upperLimit = 1000000;
        if (maximum < lowerLimit || maximum > upperLimit)
        {
            throw new ArgumentException($"{nameof(maximum)} must be between {lowerLimit:N0} and {upperLimit:N0}.");
        }
        // Create a list of consecutive integers from 1 to maximum
        var list = Enumerable.Range(1, maximum).ToList();
        // Randomize the list with a Fisher Yates shuffle.
        // The reason to impose a shuffle is to make it more challenging by not having a sorted list.
        FisherYatesShuffle(list);
        // Remove last item to spark the challenge to find the missing item.
        list.RemoveAt(list.Count - 1);
        return list;
    }

    private static Random _random = new Random();
    private static void FisherYatesShuffle(IList<int> list)
    {
        for (var i = list.Count - 1; i > 0; --i)
        {
            int swapIndex = _random.Next(0, i + 1);
            if (swapIndex != i)
            {
                var swapValue = list[i];
                list[i] = list[swapIndex];
                list[swapIndex] = swapValue;
            }
        }
    }

    private static int FindMissingNumber(IList<int> list)
    {
        ulong theoreticalSum = ((ulong)(list.Count + 1) * (ulong)(list.Count + 2)) / 2UL;
        ulong actualSum = 0;
        foreach (var value in list)
        {
            actualSum += (ulong)value;
        }
        if (actualSum == theoreticalSum)
        {
            return list.Count + 1;
        }
        else
        {
            return (int)(theoreticalSum - actualSum);
        }
    }