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

Algorithms - Warmup - Is Fibo

 Is Fibo

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

I have used the approach one suggested in this editorial . Idea is to pre compute the Fibonacci numbers upto say 60 and search if the given number is present, if present it is a Fibo number else not a Fibo Number.

Score:  15/15

/**  *  */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.ArrayList; /**  * @author Arun.G  *  */ public class Solution{        /**         * @param args         */        static BufferedReader in = new BufferedReader(new InputStreamReader(                      System.in));        static ArrayList<String> arlst = new ArrayList<String>();        public static void preCompute() {               arlst.add("0");               arlst.add("1");               for (int i = 2; i <= 60; i++) {                      BigInteger fibNum = fibonacci(BigInteger.valueOf(i));                      // if(!arlst.contains(fibNum.toString()))                      arlst.add(fibNum.toString());               }        }        //using memoization, computing using previously computed values        public static BigInteger fibonacci(BigInteger number) {               BigInteger lastFirst = new BigInteger(arlst.get(arlst.size() - 1));               BigInteger lastSecond = new BigInteger(arlst.get(arlst.size() - 2));               BigInteger third = lastFirst.add(lastSecond);               return third;        }        // Returns true if n is a Fibonacci Number, else false        public static String isFibonacci(BigInteger n) {               if (arlst.contains(n.toString()))                      return "IsFibo";               else                      return "IsNotFibo";        }        public static void main(String[] args) throws NumberFormatException,                      IOException {               // TODO Auto-generated method stub               int T = Integer.parseInt(in.readLine());               // pre-compute fibonacci numbers               preCompute();               System.out.println(arlst.toString());               for (int i = 0; i < T; i++) {                      BigInteger number = new BigInteger(in.readLine());                      System.out.println(isFibonacci(number));               }               in.close();        } }