For each number between 1 to N, we will try to find it in the given array using linear search. And if we don’t find any of them, we will return the number.

We will run a loop from 1 to N.
For each integer, we will try to find it in the given array using linear search.
For that, we will run another loop to iterate over the array and consider a flag variable to indicate if the element exists in the array. Flag = 1 means the element is present and flag = 0 means the element is missing.
Initially, the flag value will be set to 0. While iterating the array, if we find the element, we will set the flag to 1 and break out from the loop.
Now, for any number i, if we cannot find it, the flag will remain 0 even after iterating the whole array and we will return the number.

Code

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the missing number in the array
    int missingNumber(vector<int>& a, int N) {
        // Loop through numbers from 1 to N
        for (int i = 1; i <= N; i++) {
            int flag = 0; // To check if i exists in array

            // Linear search to check if i is in the array
            for (int j = 0; j < N - 1; j++) {
                if (a[j] == i) {
                    flag = 1; // i is found
                    break;
                }
            }

            // If i was not found, it is the missing number
            if (flag == 0) return i;
        }

        // Control should never reach here
        return -1;
    }
};

int main() {
    int N = 5;
    vector<int> a = {1, 2, 4, 5};

    Solution obj;
    int ans = obj.missingNumber(a, N);
    cout << "The missing number is: " << ans << endl;

    return 0;
}