Question

How to find the missing number in a list containing numbers from 1 to n in O(1) time complexity with Kotlin

Answer 1

/*
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.
*/

fun findMissingNumber(arr: IntArray): Int {
    val size = arr.size
    // formula for the sum of the first (size+1) natural numbers
    val expectedSum: Long = ((size + 1) * (size + 2) / 2).toLong()
    var actualSum: Long = 0

    for (num in arr) {
        actualSum += num.toLong()
    }

    return (expectedSum - actualSum).toInt()
}

fun main() {
    val arr = intArrayOf(1, 2, 4, 5, 6)
    val missing = findMissingNumber(arr)

    println("Missing number: $missing")
}


/*
run:

Missing number: 3

*/

 

70+ SQL courses for beginners and professionals