Missing Positive Integer
Find the
smallest positive number missing from an unsorted array .
Examples
Input: {2, 3, 7, 6, 8, -1, -10, 15}
Output: 1
Input: { 2, 3, -7, 6, 8, 1, -10, 15 }
Output: 4
Input: {1, 1, 0, -1, -2}
Output: 2
// java program to find maximum
// element
import java.util.*;
class Solution
{
/* Utility function that puts all non-positive
(0 and negative) numbers on left side of
arr[] and return count of such numbers */
static int segregate (int arr[], int size)
{
int j = 0, i;
for(i = 0; i < size; i++)
{
if (arr[i] <= 0)
{
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// increment count of non-positive
// integers
j++;
}
}
return j;
}
/* Find the smallest positive missing
number in an array that contains
all positive integers */
static int findMissingPositive(int arr[], int size)
{
int i;
// Mark arr[i] as visited by making
// arr[arr[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(Math.abs(arr[i]) - 1 < size && arr[Math.abs(arr[i]) - 1] > 0)
arr[Math.abs(arr[i]) - 1] = -arr[Math.abs(arr[i]) - 1];
}
// Return the first index value at which
// is positive
for(i = 0; i < size; i++)
if (arr[i] > 0)
return i+1; // 1 is added becuase indexes
// start from 0
return size+1;
}
/* Find the smallest positive missing
number in an array that contains
both positive and negative integers */
static int findMissing(int arr[], int size)
{
// First separate positive and
// negative numbers
int shift = segregate (arr, size);
int arr2[] = new int[size-shift];
int j=0;
for(int i=shift;i<size;i++)
{
arr2[j] = arr[i];
j++;
}
// Shift the array and call
// findMissingPositive for
// positive part
return findMissingPositive(arr2, j);
}
// main function
public static void main (String[] args)
{
Scanner sc= new Scanner(System.in);
int numInputs = Integer.parseInt(sc.nextLine());
if(numInputs>0){
int arra[] = new int[numInputs];
for (int i=0;i<numInputs ;i++ ) {
arra[i]= Integer.parseInt(sc.nextLine());
}
// int arr[] = {0, 10, 2, -10, -20};
// int arr_size = arr.length;
//int missing = findMissing(arr, arr_size);
int missing = findMissing(arra,numInputs);
System.out.println(missing);
}
}
}
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment