Question

How to find the missing number in an array containing numbers from 1 to n in O(1) time complexity with JavaScript

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

function findMissingNumber(arr) {
    const size = arr.length;
    // formula for the sum of the first (size+1) natural numbers
    const expectedSum = (size + 1) * (size + 2) / 2;
    let actualSum = 0;

    for (let i = 0; i < size; i++) {
        actualSum += arr[i];
    }

    return expectedSum - actualSum;
}

function main() {
    const arr = [1, 2, 4, 5, 6];
    const missing = findMissingNumber(arr);

    console.log("Missing number:", missing);
}

main();



/*
run:

Missing number: 3

*/

 

70+ SQL courses for beginners and professionals