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

Algorithms - Sorting - Running Time of Algorithms

Correctness and the Loop Invariant

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

Score: 1/1

/**  *  */ import java.util.Scanner; /**  * @author Arun.G  *  */ public class Solution{        /**         * @param args         */         public static int insertionSort(int[] A){              int noOfShifts=0;          for(int i = 1; i < A.length; i++){            int value = A[i];            int j = i - 1;            while(j >= 0 && A[j] > value){              A[j + 1] = A[j];              j = j - 1;             noOfShifts++; //count the number of shifts            }            A[j + 1] = value;          }                           return noOfShifts;                       }        public static void main(String[] args) {                   Scanner in = new Scanner(System.in);                   int n = in.nextInt();                   int[] ar = new int[n];                   for(int i=0;i<n;i++){                      ar[i]=in.nextInt();                   }                   System.out.println(insertionSort(ar));                                     in.close(); //close the scanner               }    }

Algorithms - Warmup - Sherlock and The Beast

 Sherlock and The Beast

The following is the solution to Hacker Rank problem Sherlock and The Beast 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; /**  * @author Arun.G  *  */ public class Solution{        /**         * @param args         */        static BufferedReader in = new BufferedReader(new InputStreamReader(                      System.in));        public static String repeat(String str, int times) {               StringBuilder ret = new StringBuilder();               for (int i = 0; i < times; i++)                      ret.append(str);               return ret.toString();        }        public static void main(String[] args) throws NumberFormatException,                      IOException {               int T = Integer.parseInt(in.readLine());               for (int i = 0; i < T; i++) {                      String s = "";                      int N = Integer.parseInt(in.readLine());                      for (int j = N; j >= 0; j--) {                            if (j % 3 == 0 && (N - j) % 5 == 0) {                                   s = repeat("5", j) + repeat("3", N - j);                                   break;                            }                      }                      if (s == "")                            System.out.println("-1");                      else                            System.out.println(s);                                           in.close();               }        } }

Algorithms - Sorting - Correctness and the Loop Invariant

Correctness and the Loop Invariant

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

The required condition for correctness of the loop invariant is to have "less than or equal to zero
"(<= 0) condition highlighted in the below code.

Score: 15/15

/**  *  */ import java.util.Scanner; /**  * @author Arun.G  *  */ public class Solution{        /**         * @param args         */         public static void insertionSort(int[] A){                 for(int i = 1; i < A.length; i++){                   int value = A[i];                   int j = i - 1;                   while(j >= 0 && A[j] > value){                     A[j + 1] = A[j];                     j = j - 1;                                      }                   A[j + 1] = value;                 }                                             printArray(A);               }                                     static void printArray(int[] ar) {                        for(int n: ar){                           System.out.print(n+" ");                        }                     }               public static void main(String[] args) {                          Scanner in = new Scanner(System.in);                          int n = in.nextInt();                          int[] ar = new int[n];                          for(int i=0;i<n;i++){                             ar[i]=in.nextInt();                          }                          insertionSort(ar);                          in.close();                      }    }

Algorithms - Warmup - Filling Jars

Filling Jars

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

Score: 20/20

/**  *  */ import java.io.BufferedReader; import java.io.InputStreamReader; import java.math.BigInteger; /**  * @author Arun.G  *  */ public class Solution{        /**         * @param args         */        public static BigInteger noOfCandies(int a, int b, int k) {               BigInteger noOfChocolates = BigInteger.ONE;                             long difference = (b-a+1);        noOfChocolates = noOfChocolates.multiply(BigInteger.valueOf(difference));               return noOfChocolates = noOfChocolates.multiply(BigInteger.valueOf(k));        }        public static void main(String[] args) {               /*                * Enter your code here. Read input from STDIN. Print output to STDOUT.                * Your class should be named Solution.                */                try                {                      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));              String[] line = br.readLine().split(" ");                      int N = Integer.parseInt(line[0]);                      int M = Integer.parseInt(line[1]);                      BigInteger noOfCandy = BigInteger.ZERO;                BigInteger average = BigInteger.ZERO;                      // M Operations to handle                      for (int i = 0; i < M; i++) {                  String[] lines = br.readLine().split(" ");                            int a = Integer.parseInt(lines[0]);                            int b = Integer.parseInt(lines[1]);                            int k = Integer.parseInt(lines[2]);                            noOfCandy = noOfCandy.add(noOfCandies(a, b, k));                      }                average = noOfCandy.divide(BigInteger.valueOf(N));                      System.out.println(average);              }              catch(Exception ex)                {                System.out.println(ex.toString());              }                             } }

Algorithms - Warmup - Halloween party

Halloween party

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

Score: 20/20

/**  *  */ import java.util.*; /**  * @author Arun.G  *  */ public class Solution{        public static long noOfChocolates(int k) {               long noOfChocolates = 0;               noOfChocolates = (long) (k / 2) * (k - (long) (k / 2));               return noOfChocolates;        }        public static void main(String[] args) {               /*                * Enter your code here. Read input from STDIN. Print output to STDOUT.                * Your class should be named Solution.                */               Scanner sc = new Scanner(System.in);               int T = sc.nextInt();               // T Test Cases to handle               for (int i = 0; i < T; i++) {                      int k = sc.nextInt();                      System.out.println(noOfChocolates(k));               }               sc.close();        } }