/*
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.
*/
object MissingNumberFinder {
def findMissingNumber(arr: Array[Int]): Int = {
val size = arr.length
// formula for the sum of the first (size+1) natural numbers
val expectedSum: Long = ((size + 1) * (size + 2)) / 2
val actualSum: Long = arr.map(_.toLong).sum
(expectedSum - actualSum).toInt
}
def main(args: Array[String]): Unit = {
val arr = Array(1, 2, 4, 5, 6)
val missing = findMissingNumber(arr)
println(s"Missing number: $missing")
}
}
/*
run:
Missing number: 3
*/
