You are given an array arr[] of N integers including 0. The task is to find the smallest positive number missing from the array.

You are given an array arr[] of N integers including 0. The task is to find the smallest positive number missing from the array.

Example 1 :-

Input :-

N = 5

arr[] = {1,2,3,4,5}

Output :- 6

Explanation :- Smallest positive missing 

number is 6.

Example 2 :-

Input :-

N = 5

arr[] = {0,-10,1,3,-20}

Output :- 2

Explanation :- Smallest positive missing 

number is 2.

Your Task :-

The task is to complete the function missingNumber() which returns the smallest positive missing number in the array.

Expected Time Complexity :- O(N).

Expected Auxiliary Space :- O(1).

Constraints :-

1 <= N <= 106

-106 <= arr[i] <= 106

JAVA

class Solution {           //Function to find the smallest positive number missing from the array. static int missingNumber(int arr[], int n) {           // Your code here for(int i=0;i<n;i++) if(arr[i]<=0)           // in this for loop we convert -ve arr[i]=n+1;           // value into n+1 for(int i=0;i<n;i++){ int k=Math.abs(arr[i]);           // store absolute value of arr[i] if(k>n) // ignore when arr[i]>n continue; if(arr[k-1]>0)           // convert arr[i] into -ve value if +ve arr[k-1]*=-1;           // if arr[i] is -ve then we just ignore } for(int k=0;k<n;k++) if(arr[k]>=0)           // if arr[i] is +ve return i+1 return k+1; return n+1; } }

C++
class Solution { public:           //Function to find the smallest positive number missing from the array. int missingNumber(int arr[], int n) {           // Your code here sort(arr,arr+n); int flag=0,index,y=1; if(n==1){ return (arr[0]>0 && arr[0]==1)? arr[0]+1 : 1; } for(int i=0;i<n;i++){ if(arr[i]>0 && flag==0){ index=i; flag=1; } } for(int i=index;i<n;i++){ if(arr[i]==y) y++; } return y; } };