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 + " ");               }        } }

Algorithms - Search- Closest Numbers

Closest Numbers

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

Score:36/36

/**  *  */ /**  *  */ import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; /**  * @author Arun.G  *  */ public class Solution{        /**         * @param args         */        static BufferedReader in = new BufferedReader(new InputStreamReader(                      System.in));          static ArrayList<Long> numArrayList = new ArrayList<Long>();        //function to print the array        static void printArray(ArrayList<Long> list)        {               for(int i=0;i<list.size();i++)               {               System.out.print(list.get(i)+"\t");               }        }   //function to get the closest numbers        static void getClosestNumbers(ArrayList<Long> list)        {               ArrayList<Long> closestNumbersList = new ArrayList<Long>();               long min = Long.MAX_VALUE;               for(int i=0;i<list.size()-1;i++)               {                      long numA = list.get(i);                      long numB = list.get(i+1);                      long diff = Math.abs(numB-numA);                      if(diff<min)//if less than min,its a new min so delete old list and add                      {                            min = diff;                            closestNumbersList.clear();                            closestNumbersList.add(numA);                            closestNumbersList.add(numB);                      }                      else if(diff==min)// this is the known min diff, add numbers to list                      {                            closestNumbersList.add(numA);                            closestNumbersList.add(numB);                      }               }               //sort the list               Collections.sort(closestNumbersList);               //print the closest numbers               printArray(closestNumbersList);        }        public static void main(String[] args) throws NumberFormatException, Exception {               // TODO Auto-generated method stub               long N = Long.valueOf(in.readLine());               String[] numbers = in.readLine().split(" ");               //get the numbers               for(int i=0;i<numbers.length;i++)               {                      long num = Long.valueOf(numbers[i]);                      numArrayList.add(num);               }               //sort the list               Collections.sort(numArrayList);               //get the closest numbers               getClosestNumbers(numArrayList);                      } }

Algorithms - Sorting- Two Arrays

 Is Fibo

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

Score: 30/30

/**  *  */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; /**  * @author Arun.G  *  */ public class Solution{        /**         * @param args         */        static BufferedReader in = new BufferedReader(new InputStreamReader(                      System.in));        public static String isTwoArray(ArrayList<Integer> a, ArrayList<Integer> b,                      int k) {               String result = "NO";               int flag = 0;               for (int i = 0; i < a.size(); i++) {                      int numRequired = k - a.get(i);                      //check if we have the exact required number                      if (b.contains(numRequired)) {                            b.remove(b.indexOf(numRequired));                            result = "YES";                            continue;                      } else {                            //check if we have at-least a number that is greater than or equal to K                            for (int j = 0; j < b.size(); j++) {                                   if (Math.abs(b.get(j) + a.get(i)) >= k) {                                          b.remove(j);                                          result = "YES";                                          flag = 1;                                          break;                                   } else                                          flag = 0;                            }                            //if flag==0 then it is not a Two Array                            if (flag == 0) {                                   result = "NO";                                   break;                            }                      }               }               return result;        }        public static void main(String[] args) throws NumberFormatException,                      IOException {               // TODO Auto-generated method stub               int T = Integer.parseInt(in.readLine());               // T Test cases               for (int i = 0; i < T; i++) {                      String[] line = in.readLine().split(" ");                      int N = Integer.parseInt(line[0]);                      int K = Integer.parseInt(line[1]);                      ArrayList<Integer> a = new ArrayList<Integer>();                      ArrayList<Integer> b = new ArrayList<Integer>();                      // get A array                      String[] stringArray = in.readLine().split(" ");                      for (int k = 0; k < stringArray.length; k++) {                            a.add(Integer.parseInt(stringArray[k]));                      }                      // get B array                      stringArray = in.readLine().split(" ");                      for (int k = 0; k < stringArray.length; k++) {                            b.add(Integer.parseInt(stringArray[k]));                      }                      Collections.sort(a);                      Collections.sort(b);                      System.out.println(isTwoArray(a, b, K));               }        } }

Algorithms - Warmup - Angry Children

Angry Children

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

Score: 30/30

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; // The part of the program involving reading from STDIN and writing to STDOUT has been provided by us. public class Solution {        static BufferedReader in = new BufferedReader(new InputStreamReader(                      System.in));        static StringBuilder out = new StringBuilder();        public static void main(String[] args) throws NumberFormatException,                      IOException {               int numPackets = Integer.parseInt(in.readLine());               int numKids = Integer.parseInt(in.readLine());               int[] packets = new int[numPackets];               for (int i = 0; i < numPackets; i++) {                      packets[i] = Integer.parseInt(in.readLine());               }               Arrays.sort(packets);               int unfairness = Integer.MAX_VALUE;               int min = Integer.MAX_VALUE, max = 0;               for (int i = 0; i < (numPackets - numKids); i++) {                      min = packets[i];                      max = packets[numKids + i - 1];                      if ((max - min) < unfairness) {                            unfairness = max - min;                      }               }               // Write your code here, to process numPackets N, numKids K, and the               // packets of candies               // Compute the ideal value for unfairness over here               System.out.println(unfairness);        } }