Find All Numbers Disappeared in an Array

Problem: Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear more than once and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array.

Example:

Input:
[2,3,2,1,2,5]

Output:
[4,6]

Approach: We can use the input array as an hash. Basically for each i = 0 to n, we make 

arr[arr[i] - 1] = - Abs(arr[arr[i] - 1]) 

With this approach, there could be a condition where when we check for arr[i], it is already negative so we just need to take the absolute value of arr[i] always. 

Once it the first loop is finished then we can have another loop to see if for any i we see arr[i] > 0 that means (i + 1) does not appear in the input array.

Implementation in C#:

        public IList<int> FindDisappearedNumbers(int[] nums)

        {

            for (int i = 0; i < nums.Length; ++i)

            {

                int index = Math.Abs(nums[i]) - 1;

                nums[index] = -Math.Abs(nums[index]);

            }

            List<int> result = new List<int>();

            for (int i = 0; i < nums.Length; ++i)

            {

                if (nums[i] > 0)

                {

                    result.Add(i + 1);

                }

            }

            return result;

        }

Complexity: O(n)