Get a different number - being interviewer -

GetADifferentNumber_BeingInterviewer.cs

using System;
using System.Collections.Generic;

/// [0, 3, 2, 1]
/// [0, 2, 1, ]
/// iterate starting from 0 --> inc 1 --> 

class Solution
{
    public static int GetDifferentNumber(int[] arr)
    {
      var set = new HashSet<int>();
      
      foreach(var element in arr){
        set.Add(element);
      }
      
      for(int i = 0; i < arr.Length + 1; i++) {
        if(!set.Contains(i)) {
          return i;
        }
      }
      
      // should not reach here ever.
      return -1;
    }

    /// can modify the array 
    public static int GetDifferentNumber2(int[] arr)
    {
      for(int i = 0; i < arr.Length; i++) {
        var current = arr[i];
        
        if(current < arr.Length && current != i){
          int temp = arr[current];
          arr[current] = current;
          arr[i] = temp;
        }
      }
      
      for(int i = 0; i < arr.Length; i++) {
        if(i != arr[i]){
          return i;
        }
      }
      
      return arr.Length;
    }
    
    static void Main(string[] args)
    {

    }
}