Find_All_Missing_Numbers.cpp

/*
Problem Statement: We are given an unsorted array containing numbers taken from the range 1 to ‘n’. The array can have duplicates, which means some numbers will be missing. Find all those missing numbers.

Input: [2, 3, 1, 8, 2, 3, 5, 1]
Output: 4, 6, 7
Explanation: The array should have all numbers from 1 to 8, due to duplicates 4, 6, and 7 are missing.
*/

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


void swap(vector<int> &nums, int i, int j)
{
    int temp=nums[i];
    nums[i]=nums[j];
    nums[j]=temp;
}

vector<int> find_all_missing_numbers(vector<int> &nums)
{
    int i=0;
    vector<int> result;
    while(i<=nums.size())
    {
        if(nums[i]<=nums.size() && nums[i]!=nums[nums[i]])
        {
            swap(nums,i,nums[i]);
        }
        else
        {
            i++;
        }
    }

    for(int i=1;i<=nums.size();i++)
    {
        if(i!=nums[i])
        {
            result.push_back(i);
        }
    }
    return result;
}


int main()
{
    vector<int> input={1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,13,1,5,2,1,3,9,5,5,12,13,24,12,12,13,14,12,13,14,12,13,12,14,13,12,48};
    cout<<input.size();
    for(auto res:find_all_missing_numbers(input))
    {
        cout<<res<<" ";

    }
}

/*
Time Complexity : O(N) as we are swapping and iterating through the array for n times
O(N) (While loop )+ O(N-1)(swapping)+O(1)(i++)


Space Complexity is O(1)
*/