Advertisement
gelita

Find missing numbers in array through n

Feb 8th, 2020
211
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 1.44 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class MyCode {
  5.  
  6.  
  7. /**
  8.     * 4 Missing Number
  9.     *
  10.     * Given range of 1 to N and an array of unique integers that are within that
  11.     * range, return the missing integers not found in the array
  12.     *
  13.     * Parameters
  14.     * Input: n {Integer}
  15.     * Input: arr {Array of Integers}
  16.     * Output: {ArrayList of Integers}
  17.     *
  18.     * Constraints
  19.     * Time: O(N)
  20.     * Space: O(N)
  21.     *
  22.     * Examples
  23.     * `4, [1, 4, 2] --> [3]`
  24.     * `8, [4, 7, 1, 6] --> [2, 3, 5, 8]`
  25.     * `6, [6, 4, 2, 1] --> [3, 5]`
  26.     */
  27.    public static void main (String[] args) {
  28.        
  29.     int[] arr = new int[]{1,4,2,3};
  30.     ArrayList<Integer> list = new ArrayList<Integer>();
  31.     list = missingNumber(9, arr);
  32.     System.out.println(list);
  33.     }
  34.    
  35.  
  36.     public static ArrayList<Integer> missingNumber(int n, int[] arr) {
  37.       int max = n; //for readability
  38.       Arrays.sort(arr);
  39.       //get min from the sorted input array
  40.       int min = arr[0];
  41.       int len = n - min +1;
  42.       ArrayList<Integer> list = new ArrayList<Integer>();
  43.       HashSet<Integer> set = new HashSet<Integer>();
  44.       for(int i = 0; i < arr.length; i++){
  45.        set.add(arr[i]);
  46.       }
  47.       for(int index = min; index < max; index++)
  48.         if(!set.contains(index)){
  49.           list.add(index);
  50.       }
  51.       if(!set.contains(max)){
  52.         list.add(max);
  53.       }
  54.       System.out.println(list);
  55.       return list;
  56.     }
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement