Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/929f1494e6ac421d3d71962e3b65fae5 to your computer and use it in GitHub Desktop.
Save jianminchen/929f1494e6ac421d3d71962e3b65fae5 to your computer and use it in GitHub Desktop.
Getting a different number - cannot change the array
using System;
class Solution
{
public static int GetDifferentNumber(int[] arr) // [0, 1, 2, 3]
{
if(arr == null || arr.Length == 0) //false
{
return 0;
}
int length = arr.Length; // 4
var found = scanArraySaveFound(arr); //
// go over the found array to find first missing one
for(int i = 0; i < length; i++)
{
if(found[i] == 0) // found[i], not arr[i] -
{
return i;
}
}
return length; // 4
}
private static int[] scanArraySaveFound(int[] arr)
{
int length = arr.Length;
var found = new int[length]; // 4
for(int i = 0 ; i < length; i++) // [0, 1, 2, 3]
{
var number = arr[i]; // 0
if(number >= length) // 4
{
continue;
}
found[number] = 1; // found[0] = 1
}
return found;
}
static void Main(string[] args)
{
Console.WriteLine(GetDifferentNumber(new int[]{0, 1, 2, 3})) ;
}
}
// [0, 1, 2, 3] -
// 4
// array size 4
// int[4] - 0
// index = 0,
// found[index] = 1, found[2] = 1, > 4,
// scan minimum index with 0 -> size = 4
// O(n) space, time complexity O(n)
//
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment