Imports System
Module MissingNumberFinder
'
' The essence of O(1) space complexity is that the algorithm uses a fixed amount of memory,
' regardless of input size. Time complexity here is O(n) because we must scan the array.
'
Function FindMissingNumber(arr As Integer()) As Integer
Dim size As Integer = arr.Length
' formula for sum of first (size+1) natural numbers
Dim expectedSum As Long = CLng(size + 1) * (size + 2) \ 2
Dim actualSum As Long = 0
For i As Integer = 0 To size - 1
actualSum += arr(i)
Next
Return CInt(expectedSum - actualSum)
End Function
Sub Main()
Dim arr As Integer() = {1, 2, 4, 5, 6}
Dim missing As Integer = FindMissingNumber(arr)
Console.WriteLine("Missing number: " & missing)
End Sub
End Module
'
' run:
'
' Missing number: 3
'
