find the first missing positive in unsorted array

#include <stdio.h> #include<stdlib.h> int fmp(int [] ,int); //function for first missing positive int main() { int a[100000],n,i,j,temp; scanf("%d",&n); for(i=0;i<=n-1;i++) { scanf("%d",&a[i]); //array scan } j=0; for(i=0;i<=n-1;i++) //loop for separating +ve and -ve { if(a[i]<=0 ) { temp=a[i]; a[i]=a[j]; a[j]=temp; j++; } } int val=fmp(a+j,n-j); // calling fmp printf("%d",val); return 0; }

int fmp( int a[],int n) // fmp definiton { int i,size=n; // Mark a[i] as visited by making a[a[i] - 1] negative. // Note that 1 is subtracted because index start // from 0 and positive numbers start from 1 for(i = 0; i < size; i++) { if((a[i]) - 1 < size && a[(a[i]) - 1] > 0) a[ (a[i]) - 1] = -a[(a[i]) - 1]; } // Return the first index value at which is positive for(i = 0; i < size; i++) if (a[i] > 0) return i+1; // 1 is added because indexes start from 0

//any +ve more than size-1. return size+1; //no integer more than size-1 }

Time complexity:O(n)     space complexity:O(1)