Question

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

Answer 1

package main

import "fmt"

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

func findMissingNumber(slice []int) int {
    size := len(slice)
    // formula for the sum of the first (size+1) natural numbers
    expectedSum := (size + 1) * (size + 2) / 2
    actualSum := 0

    for i := 0; i < size; i++ {
        actualSum += slice[i]
    }

    return expectedSum - actualSum
}

func main() {
    slice := []int{1, 2, 4, 5, 6}
    missing := findMissingNumber(slice)

    fmt.Printf("Missing number: %d\n", missing)
}



/*
run:

Missing number: 3

*/

 

70+ SQL courses for beginners and professionals