Find missing number between 1 to 100 in unsortedArray - consume less memory in java


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.




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
*/


Previous program                                                                  Next program



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



No comments:

Post a Comment