Algorithms - Search- Missing Numbers

Missing Numbers

The following is the solution to Hacker Rank problem Missing Numbers using Java.  For solutions to other Hacker Rank Problem visit my page HackerRank, alternatively try searching for the problem in my blog.

I'm using the following approach:

 since the two lists are sorted I'm comparing element in array  A with element in array B of the same index.

203 205

▲

203 204 205

▲

If they are same, moving to next index as they are not missing numbers.

203 205

      ▲

203 204 205

      ▲

if the elements are not same, it means it is a missing number, so adding 204 to list and moving B's index to next.

203 205

      ▲

203 204 205

              ▲

Again if it is same move to next index else add the missing numbers. If the A array length is reached all the elements now in B after the current index are missing so all of these are missing numbers.

Sort the missing list and display and don't forget the list should not have duplicates.

Score:40/40

/**  *  */ import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.List; /**  * @author Arun.G  *  */ public class Solution{        /**         * @param args         */        static BufferedReader in = new BufferedReader(new InputStreamReader(                      System.in));        public static void main(String[] args) throws NumberFormatException,                      Exception {               /*                * Enter your code here. Read input from STDIN. Print output to STDOUT.                * Your class should be named Solution.                */               int n = Integer.parseInt(in.readLine());               List<Integer> A = new ArrayList<Integer>();               List<Integer> B = new ArrayList<Integer>();               ArrayList<Integer> missingNumbersList = new ArrayList<Integer>();               //get all the numbers in A list               String[] ANumbers = in.readLine().split(" ");               for (int i = 0; i < ANumbers.length; i++) {                      A.add(Integer.parseInt(ANumbers[i]));               }               //sort the A List               Collections.sort(A);               //get all the numbers in B list               int m = Integer.parseInt(in.readLine());               String[] BNumbers = in.readLine().split(" ");               for (int i = 0; i < BNumbers.length; i++) {                      B.add(Integer.parseInt(BNumbers[i]));               }               //sort the A List               Collections.sort(B);                             int i = 0, j = 0;               while (i < B.size()) {                      if (j < A.size()) {                            int numB = B.get(i);                            int numA = A.get(j);                            if (numA == numB) {                                   i++;                                   j++;                            } else {                                   if (!missingNumbersList.contains(numB))                                          missingNumbersList.add(numB);                                   i++;                            }                      } else {                            if (!missingNumbersList.contains(B.get(i)))                                   missingNumbersList.add(B.get(i));                            i++;                      }               }               Collections.sort(missingNumbersList);               for (Integer num : missingNumbersList) {                      System.out.print(num + " ");               }        } }