Find a missing number from an array 🫙

Theory to get started

In this problem we take an optimal approach to just find the sum of entire range, and the sum of all the elements present in the array and in the end we subtract the sum of entire elements from the sum of the range of array.

Step 1: find the sum of entire range using sum = (N * (N+1))/2 formula

Step 2: find the sum of all elements inside an array

Step-3: Doing step1 - step2 will get you your answer

Continue the steps above until your reach end of an array.

Here is the breakdown of the steps in the code:

    /* 
        https://leetcode.com/problems/missing-number/
    */

    #include <stdio.h>
    #include <iostream>
    #include <vector>

    using namespace std;

    int getMissingNumber(vector<int>&arr){
        /* Step1: find the sum of entire range using 
            sum = (N * (N+1))/2 formula
        */
        int size = arr.size();
        int sumOfArrRange = (size * (size + 1))/2;

        /* 
            Step2: find the sum of all elements inside an array 
        */
        int sumOfArrNums = 0;
        for(int i=0; i < size; i++){
            sumOfArrNums += arr[i];
        }
        /* step1 - step2 is your answer */
        return sumOfArrRange - sumOfArrNums;
    }

    int main(){
        int n;
        cin >> n;

        vector<int> arr(n);
        for(int i=0; i<arr.size(); i++){
            cin >> arr[i];
        }

        int ans = getMissingNumber(arr);
        cout << ans;
        return 0;
    }

[Top]