FindDisappearedNumbers 4 solutions. bitmask / shuffle / negative shift / bit array

141

That was a lot of fun, here are the solutions I wrote

I'm quite pleased with this one as I thought it up myself.
I derived the idea from observing how others had used
a negative value to mark the index.

    // my recipe.  The other crazy thing about this problem
    // is that if we weren't finding the disapeared this acts
    // as a duplicate removing sort!  see //*comment
    public IList<int> FindDisappearedNumbers(int[] nums)
    {
        // as problem states 1 <= n <= 10^5
        // we have plenty of spare bits to create a mask
        // probly a better way, but this is visually clear.
        const int mask1 = 0b1_0000_0000_0000_0000_0000;
        const int mask2 = 0b0_1111_1111_1111_1111_1111;
        for (int i = 0; i < nums.Length; i++)
        {
            int j = (mask2 & nums[i]) - 1;
            nums[j] = mask1 | nums[j];
        }

        var list = new List<int>();
        for (int i = 0; i < nums.Length; i++)
        {
            if ((nums[i] & mask1) == 0) //*change to > 0 for sort
            {
                list.Add((mask2 & i) + 1);
            }
        }
        return list;
    }

In place solution
I'm not sure what to call this one. its like one of those sliding puzzles

    // in place fun
    public IList<int> FindDisappearedNumbers2(int[] nums)
    {      
        int mark = nums.Length;

        // for my sanity!
        for (int i = 0; i < mark; i++)
        {
            nums[i]--;
        }

        {
            int i = 0;

            while (i < mark)
            {
                if (nums[i] == i || nums[i] == mark)
                {
                    i++;
                    continue;
                }

                if (nums[nums[i]] == mark)
                {
                    nums[nums[i]] = nums[i];
                    nums[i] = mark;
                    i++;
                    continue;
                }

                if (nums[nums[i]] == nums[i])
                {
                    nums[i] = mark;
                    i++;
                    continue;
                }

                if (nums[nums[i]] == i)
                {
                    nums[nums[i]] = nums[i];
                    nums[i] = i;
                    i++;
                    continue;
                }

                else
                {
                    (nums[i], nums[nums[i]]) = (nums[nums[i]], nums[i]);
                    continue;
                }
            }
        }
        
        var list = new List<int>();
        for (int i = 0; i < mark; i++)
        {
            if (nums[i] == mark)
            {
                list.Add(i + 1);
            }
        }
        return list;
    }

Not my original idea but a beauty which inspired me.

    // wish I thought of this one!
    public IList<int> FindDisappearedNumbers3(int[] nums)
    {
        for (int i = 0; i < nums.Length; i++)
        {
            int j = Math.Abs(nums[i]) - 1;
            // idempotent
            nums[j] = -Math.Abs(nums[j]);
        }
        
        var list = new List<int>();
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] > 0)
            {
                list.Add(i + 1);
            }
        }
        return list;
    }

my first attempt with a BitArray

    // with extra allocation
    public IList<int> FindDisappearedNumbers1(int[] nums)
    {
        var bits = new BitArray(nums.Length, true);
        
        for(int i = 0; i < nums.Length; i++)
        {
            bits[nums[i]-1] = false;
        }
        
        var list = new List<int>();
        
        for(int i = 0; i < bits.Length; i++)
        {
            if(bits[i])
            {
                list.Add(i+1);
            }
        }
        
        return list;
    }

Comments (0)