ArraysEasy

Find the Missing Number in Array

Problem Statement:Given an array arr[] of size n-1 with distinct integers in the range of [1, n]. This array represents a permutation of the integers from 1 to n with one element missing. Find the missing element in the array.

JavaScript Solution & Complexity Analysis

Run & test in browser
JavaScript Lab Sandbox
/*
Problem Statement -> Given an array arr[] of size n-1 with distinct integers in the range of [1, n]. This array represents a permutation of the integers from 1 to n with one element missing. Find the missing element in the array.

Approach 1 (Brute Force) -> Run nested loop for element 1 to n, for each element check weather that element is present in array or not till the last iteration.

Approach 2 (Optimal Approach) -> take the sum of the array then use standard formula n*((n+1)/2) to calculate the sum of n number then subtract the sum of current array from sum of n number, where n will be the length of array.
*/

function findTheMissingNumberApproach3(arr) {
  /*
    TC - O(N)
    SC - O(1)
  */
  let arrLength = arr.length,
    sum = 0,
    expectedSum = 0;
  for (let i = 0; i < arrLength; i++) {
    sum += arr[i];
  }
  arrLength = arrLength + 1;
  expectedSum = (arrLength * (arrLength + 1)) / 2;
  return expectedSum - sum;
}

const testCase1 = [8, 2, 4, 5, 3, 7, 1];
console.log(
  "Test case 1 Approach 3 result:",
  findTheMissingNumberApproach3(testCase1),
);
Console Output
Click "Run Code" above to execute and view output...