Smallest Positive missing number Constant Space

Smallest Positive missing number Constant Space

  January 16, 2019    

---

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

Here we can use negation technique where if one element is encountered then we just negate its index value and again iterate through the array and find which index is positive and that index+1 number is answer as index starts from 0.

Before this we need to filter negative elements as we need to find missing number > 0 , so partition number such that all numbers greater than 0 are at left side.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class dmg
 {
     public static int partition(int a[],int n)
     {
         int r=n-1;
         for(int i=n-1;i>=0;--i)
         {
             if(a[i]<=0)
             {
                 int temp=a[r];
                 a[r]=a[i];
                 a[i]=temp;
                 --r;
             }
         }
         return r;
     }
  public static int fn(int a[],int n)
  {
      int p=partition(a,n);
      //System.out.println(p+" ");
       /*for(int i=0;i<=p;++i)
      {
           System.out.print(a[i]+" ");
      }*/
      for(int i=0;i<=p;++i)
      {
          if(Math.abs(a[i])-1<=p  && a[Math.abs(a[i])-1]>0)
          a[Math.abs(a[i])-1]=-a[Math.abs(a[i])-1];
      }
      /*for(int x:a)
      System.out.print(x+" ");*/
       for(int i=0;i<=p;++i)
      {
          if(a[i]>0)
          return i+1;
      }
      return p+2;
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    System.out.println(fn(arr,n));
}
}

}