Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- class MyCode {
- /**
- * 4 Missing Number
- *
- * Given range of 1 to N and an array of unique integers that are within that
- * range, return the missing integers not found in the array
- *
- * Parameters
- * Input: n {Integer}
- * Input: arr {Array of Integers}
- * Output: {ArrayList of Integers}
- *
- * Constraints
- * Time: O(N)
- * Space: O(N)
- *
- * Examples
- * `4, [1, 4, 2] --> [3]`
- * `8, [4, 7, 1, 6] --> [2, 3, 5, 8]`
- * `6, [6, 4, 2, 1] --> [3, 5]`
- */
- public static void main (String[] args) {
- int[] arr = new int[]{1,4,2,3};
- ArrayList<Integer> list = new ArrayList<Integer>();
- list = missingNumber(9, arr);
- System.out.println(list);
- }
- public static ArrayList<Integer> missingNumber(int n, int[] arr) {
- int max = n; //for readability
- Arrays.sort(arr);
- //get min from the sorted input array
- int min = arr[0];
- int len = n - min +1;
- ArrayList<Integer> list = new ArrayList<Integer>();
- HashSet<Integer> set = new HashSet<Integer>();
- for(int i = 0; i < arr.length; i++){
- set.add(arr[i]);
- }
- for(int index = min; index < max; index++)
- if(!set.contains(index)){
- list.add(index);
- }
- if(!set.contains(max)){
- list.add(max);
- }
- System.out.println(list);
- return list;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement