10
\$\begingroup\$

I just encountered this question in codility but apparently this question has been asked in 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.

\$\endgroup\$
  • 4
    \$\begingroup\$ This question becomes much more interesting if the elements are not integers, but rather are distinct objects that can be compared for equality, and that's all. If you know they are integers and one is missing, you just sum the integers with one missing, sum the integers with none missing, and the difference of the two sums is obviously the missing integer. \$\endgroup\$ – Eric Lippert May 25 '16 at 15:28
  • 1
    \$\begingroup\$ Use an array of bools and set each index to true as you find that index in the permutation. Whichever leftover element is false is the missing element. This is O(N) space instead of the required O(1) space. The trick is to use a virtual array of bools by flipping the sign bit on the input array elements (if the array elements were signed, we could mark elements as true by adding array.length to corresponding index instead). \$\endgroup\$ – Brian May 25 '16 at 18:46
22
\$\begingroup\$

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;
    }
\$\endgroup\$
  • 2
    \$\begingroup\$ I think using long isn't necessary. Even if n*(n + 1)/2 overflows, it will overflow in the same way as the real sum. \$\endgroup\$ – Tavian Barnes May 25 '16 at 20:43
  • 2
    \$\begingroup\$ @TavianBarnes You are right I think, well spotted. The only problem is the Sum() method always does overflow checking so you would have to replace it with .Aggregate(0, (sum, i) => sum + i). Also using longs might be needed if there's a chance the code would be run in a checked block or in a project with overflow checking turned on. \$\endgroup\$ – gfv May 26 '16 at 9:31
11
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Good idea! You don't have have an if statement for an empty array because the algorithm will return the correct value, which is 1. This solution can be made into a one-liner with LINQ: return Enumerable.Range(1, values.Count() + 1).Concat(values).Aggregate(0, (x, y) => x ^ y); \$\endgroup\$ – Risky Martin May 26 '16 at 2:07
  • \$\begingroup\$ No need for two loops if you start with int result = values.Length; then the loop body can simply be result ^= i ^ values[i];. \$\endgroup\$ – Toby Speight Dec 3 '18 at 15:33
3
\$\begingroup\$

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;

}
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$ – Toby Speight Dec 3 '18 at 15:19
2
\$\begingroup\$

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

}
\$\endgroup\$
  • \$\begingroup\$ The O notation is depending on the range of elements in the array, if the element is less than 16 - Insertion sort (O(N)) and more than Quick sort -(O(n log n) ). this is just an estimate for the best case performance \$\endgroup\$ – Siobhan May 25 '16 at 11:38
  • \$\begingroup\$ Brilliant, this solved my problem \$\endgroup\$ – Siobhan May 25 '16 at 12:10
  • \$\begingroup\$ Maybe an over-optimization, but how about a binary search on the sorted list, instead of a linear search? \$\endgroup\$ – cdkMoose May 25 '16 at 13:28
  • 7
    \$\begingroup\$ I'm confused, how does this solve the original problem when sorting is O(n log n) and the problem statement requires O(n) worst case complexity? \$\endgroup\$ – stannius May 25 '16 at 16:03
  • \$\begingroup\$ You called Array.Sort but that has a worst case of O(n^2). This is no where near the required O(N) complexity. Also, you didn't consider if the array has duplicates. \$\endgroup\$ – whiteshooz Dec 1 '18 at 23:50
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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);
        }
    }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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