You are here : Home / Core Java Tutorials / Interview Programs (beginner to advanced) in java / Level3 programs in java (advanced)
In this core java programming tutorial we will write following program in java >
Program 1 to Find first missing positive number in an unsorted array in java.
You are given an unsorted array of positive and negative numbers, find first missing positive number from that unsorted array in java
Logic will be>
- sort the array - we will use Merge sort to offer best complexity.
For sorting the array we will use merge sort which offers one of the best complexity i.e. O(N*logN)
- find the index of first positive number.
- Than iterate from firstPositiveNumberIndex till first positive number is not missing.
complexity i.e. O(N)
Overall complexity of program will be O(N*logN) + O(N) in java.
This program could also be a simple Level2 program but I have kept this as Level3 program because I am using merge sort for sorting.
Using sorting algorithm like Bubble Sort, Selection Sort and Insertion Sort will offer o(n2) complexity.
Example in java -
{3,0,1,8,-1,7,-11,10} - 2 is missing
{1, -2, 3, 5, 4, 2 , -4} - No number is missing
{1, -2, 3, -9, 0, 8, -90,2} - 4 is missing
{1, 0, 2 } - No number is missing
{1, 0, 2, 4} - 3 is missing
Program/ Example 1 to Find first missing positive number in an unsorted array in java.
/** Copyright (c), AnkitMittal JavaMadeSoEasy.com */
public class FindFirstMissingPositiveNumber {
static int ar[]={0,1,2,-2,5,7,3,4}; //6 is missing
public static void main(String[] args) {
//first sort array - we will use Merge sort
int[] ar2 = new int[ar.length];
mergeSort(ar2, 0, ar.length - 1);
//display array
display();
//Now let's find first missing positive number
findFirstMissingPositiveNumber();
}
static void findFirstMissingPositiveNumber(){
int firstPositiveNumberIndex = -1;
for(int i=0;i<ar.length;i++){
//Enter if loop only when we have already found index of first positive number
if(firstPositiveNumberIndex > -1){
//iterate from firstPositiveNumberIndex till first positive number is not missing
if( (i-firstPositiveNumberIndex+1) != ar[i]){
System.out.println( (i-firstPositiveNumberIndex+1) + " is missing");
return;
}
}
//Find index of first positive number
else if(ar[i] >=1){
if(ar[i]!=1){
System.out.println("1 is missing");
return;
}
firstPositiveNumberIndex = i;
}
}
System.out.println("No number is missing");
}
/*
* method performs merge sort.
*/
static void mergeSort(int[] workSpace, int lowerBound, int upperBound) {
if (lowerBound == upperBound){
return; //no need to sort further.
}else { // finding mid point
int midPoint = (lowerBound + upperBound) / 2;
mergeSort(workSpace, lowerBound, midPoint); // sorting low half
mergeSort(workSpace, midPoint + 1, upperBound); // sort upper half
merging(workSpace, lowerBound, midPoint + 1, upperBound) - merging them
}
}
static void merging(int[] ar2, int low, int high, int upperBound) {
int midPoint = high - 1;
int lowerBound = low;
int n = upperBound - lowerBound + 1;
int i = 0;
while (low <= midPoint && high <= upperBound)
if (ar[low] < ar[high])
ar2[i++] = ar[low++];
else
ar2[i++] = ar[high++];
while (low <= midPoint)
ar2[i++] = ar[low++];
while (high <= upperBound)
ar2[i++] = ar[high++];
for (i = 0; i < n; i++)
ar[lowerBound + i] = ar2[i];
}
static void display(){
for(int i=0;i<ar.length;i++){
System.out.print(ar[i]+" ");
}
System.out.println();
}
}
/*OUTPUT
-2 0 1 2 3 4 5 7
6 is missing
*/
|
Note : 1 is the first positive number, not zero.
Program/ Example 2 to Find first missing positive number in an unsorted array which may consist of duplicate numbers in java.
Logic and complexity of program will be same as above program.
Example -
{0,1,2,-2,5,7,3,1,4} - 6 is missing
{3,0,1,8,-1,7,1,-11,10} - 2 is missing
{1,2,3,1} - No number is missing
{ 1, -2, -9, 0, 8, 7, 5, 6, 0, 1, -1, -90, 2, 2, 2, 4 } - 3 is missing
/** Copyright (c), AnkitMittal JavaMadeSoEasy.com */
public class FindFirstMissingPositiveNumberDuplicateNumbers {
static int ar[] = {1, -2, -9, 0, 8, 7, 5, 6, 0, 1, -1, -90, 2, 2, 2, 4 } - 3 is missing
public static void main(String[] args) {
//first sort array - we will use Merge sort
int[] ar2 = new int[ar.length];
mergeSort(ar2, 0, ar.length - 1);
//display array
display();
//Now let's find first missing positive number
findFirstMissingPositiveNumber();
}
static void findFirstMissingPositiveNumber(){
int firstPositiveNumberIndex = -1;
for(int i=0;i<ar.length;i++){
//Enter if loop only when we have already found index of first positive number
if(firstPositiveNumberIndex > -1){
//Just add small logic here to detect number is same as previous or not
if(ar[i]== ar[i-1]){
//Increase firstPositiveNumberIndex to counter the duplicate numbers in array
firstPositiveNumberIndex++;
continue;
}
//iterate from firstPositiveNumberIndex till first positive number is not missing
if( (i-firstPositiveNumberIndex+1) != ar[i]){
System.out.println( (i-firstPositiveNumberIndex+1) + " is missing");
return;
}
}
//Find index of first positive number
else if(ar[i] >=1){
if(ar[i]!=1){
System.out.println("1 is missing");
return;
}
firstPositiveNumberIndex = i;
}
}
System.out.println("No number is missing");
}
/*
* method performs merge sort.
*/
static void mergeSort(int[] workSpace, int lowerBound, int upperBound) {
if (lowerBound == upperBound){
return; //no need to sort further.
}else { // finding mid point
int midPoint = (lowerBound + upperBound) / 2;
mergeSort(workSpace, lowerBound, midPoint); // sorting low half
mergeSort(workSpace, midPoint + 1, upperBound); // sort upper half
merging(workSpace, lowerBound, midPoint + 1, upperBound) - merging them
}
}
static void merging(int[] ar2, int low, int high, int upperBound) {
int midPoint = high - 1;
int lowerBound = low;
int n = upperBound - lowerBound + 1;
int i = 0;
while (low <= midPoint && high <= upperBound)
if (ar[low] < ar[high])
ar2[i++] = ar[low++];
else
ar2[i++] = ar[high++];
while (low <= midPoint)
ar2[i++] = ar[low++];
while (high <= upperBound)
ar2[i++] = ar[high++];
for (i = 0; i < n; i++)
ar[lowerBound + i] = ar2[i];
}
static void display(){
for(int i=0;i<ar.length;i++){
System.out.print(ar[i]+" ");
}
System.out.println();
}
}
/*OUTPUT
-2 0 1 2 3 4 5 7
6 is missing
*/
|
Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.
RELATED LINKS>