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 a program to Find missing number between 1 to 100 in unsortedArray - consume less memory in java.
Read : Find missing number between 1 to 100 in unsortedArray - in one iteration in java - consume more memory in java.
Logic>
First, we will use mergeSort to sort the array. Then, we will iterate from 1 to 100 (keep it in variable i) and compare i with sorted array and find out missing numbers.
if i is not found in ar means number is missing.
Complexity of using merge sort will be O(nlogn)
complexity of iterating from 1 to 100 will be O(n).
so overall complexity of our operation will be O(nlogn) + O(n).
And we won’t be consuming any extra memory (though we will consume bit of extra memory used by mergeSort in sorting).
Full Program/SourceCode / Example in java to Find missing number between 1 to 100 in unsorted Array - consume less memory >
/** Copyright (c), AnkitMittal JavaMadeSoEasy.com */
public class FindMissingNumberInUnSortedArray{
static int ar[]={3,7,5,8,44,24}; //given array
public static void main(String[] args) {
System.out.print("given array : ");
for (int j = 0; j < ar.length; j++)
System.out.print(ar[j] +" "); // display it
mergeSortWrapper();
displayMissing();
}
static void mergeSortWrapper(){
int ar2[]=new int[ar.length];
mergeSort(ar2,0,ar.length-1);
}
static void mergeSort(int ar2[],int lowBound,int highBound){
int mid;
if(lowBound==highBound)
return;
else
mid=(lowBound+highBound)/2;
mergeSort(ar2, lowBound, mid); //sort lower
mergeSort(ar2, mid+1, highBound);//sort upper
merging(ar2,lowBound,mid+1,highBound);
}
static void merging(int ar2[],int lowBound,int highPtr,int highBound){
int j=lowBound;
int lowptr=highPtr-1;
int n=highBound-lowBound+1;
int lowBoundCount=lowBound;
while(lowBound<=lowptr && highPtr<=highBound){
if(ar[lowBound]<ar[highPtr])
ar2[j++]=ar[lowBound++];
else
ar2[j++]=ar[highPtr++];
}
while(lowBound<=lowptr)
ar2[j++]=ar[lowBound++];
while(highPtr<=highBound)
ar2[j++]=ar[highPtr++];
for(int i=lowBoundCount;i<lowBoundCount+n;i++)
ar[i]=ar2[i];
}
/*
* Method for displaying missing number in given range.
*/
static public void displayMissing(){
System.out.print("\nArray after sorting: ");
for (int j = 0; j < ar.length; j++)
System.out.print(ar[j] +" "); // display it
System.out.print("\nAs array is sorted, its easy to find missing numbers now");
System.out.print("\nNumbers missing between 1 to 100 in array : ");
int j=0;
for(int i=1;i<=100;i++){
if(j<ar.length && i==ar[j])
j++;
else
System.out.print(i+" ");
}
}
}
/*OUTPUT
given array : 3 7 5 8 44 24
Array after sorting: 3 5 7 8 24 44
As array is sorted, its easy to find missing numbers now
Numbers missing between 1 to 100 in array : 1 2 4 6 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
*/
|
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>
>Pattern/Pyramid generating programs
Labels:
Core Java
Level3 programs (advanced)