Posts for: #Java

HackerRank Contest - Project Euler - Largest product in a series

#HackerRank  #Solution  #Java 

Solution

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        
        for(int j=0;j<T;j++){
            int N = scan.nextInt();
            int K = scan.nextInt();
            scan.nextLine();
        
            char[] data = scan.nextLine().toCharArray();
        
            int max = 0;
        
            for(int i=0;i<N-K;i++){
                int prod = getProduct(data,i,K);
            
                if(prod>max){
                    max = prod;
                }
            }
        
            System.out.println(max);
        }
        
    }
    
    static int getProduct(char[] data, int start, int length){
        int product = 1;
        
        for(int i=start;i<start+length;i++){
            product = product * Character.getNumericValue(data[i]);
        }
        
        return product;
    }
}

HackerRank Contest - Project Euler - Multiples of 3 and 5

#HackerRank  #Solution  #Java 

Solution

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        
        Scanner scan  = new Scanner(System.in);
        int numCases = scan.nextInt();
        
        for(int index=0;index<numCases;index++){
            long num = scan.nextInt()-1;
            
            System.out.println(sumOfMultiples(num/3,3)+sumOfMultiples(num/5,5)-sumOfMultiples(num/15,15));
        }
    }
    
    public static long sumOfMultiples(long num, long multiple){
        return (multiple*num*(num+1))/2;
    }
}

HackerRank - Divisible Sum Pairs

#HackerRank  #Solution  #Java 

Solution

/* Solution to HackerRank: Divisible Sum Pairs
 * URL: https://www.hackerrank.com/challenges/divisible-sum-pairs
 */
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the divisibleSumPairs function below.
    static int divisibleSumPairs(int n, int k, int[] ar) {
        int count = 0;
        
        for(int i=0; i < n; i++){
            for(int j=i+1; j < n; j++){
                if((ar[i]+ar[j])%k == 0){
                    count++;
                }
            }
        }

        return count;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nk = scanner.nextLine().split(" ");

        int n = Integer.parseInt(nk[0]);

        int k = Integer.parseInt(nk[1]);

        int[] ar = new int[n];

        String[] arItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            int arItem = Integer.parseInt(arItems[i]);
            ar[i] = arItem;
        }

        int result = divisibleSumPairs(n, k, ar);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

HackerRank - The Time in Words

#HackerRank  #Solution  #Java 

Solution

/* Solution to HackerRank: The Time in Words
 * URL: https://www.hackerrank.com/challenges/the-time-in-words
 */
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the timeInWords function below.
    static String timeInWords(int h, int m) {
        String[] words = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen", "twenty"};
        
        if (m == 0){
            return words[h] + " o' clock";
        } else if (m == 15){
            return "quarter past " + words[h];
        } else if (m == 30){
            return "half past " + words[h];
        } else if (m == 45){
            return "quarter to " + words[h+1];
        } else if (m == 1){
            return "one minute past " + words[h];
        } else if (m == 59){
            return "one minute to " + words[h+1];
        } else if (m < 21){
            return words[m] + " minutes past " + words[h];
        } else if (m > 39){
            return words[60-m] + " minutes to " + words[h+1];
        } else if (m > 30){
            return "twenty " + words[(60-m)%20] + " minutes to " + words[h+1];
        }
        else{            
            return "twenty " + words[m%20] + " minutes past " + words[h];
        }

    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int h = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        int m = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        String result = timeInWords(h, m);

        bufferedWriter.write(result);
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

HackerRank Contest - Project Euler - Large Sum

#HackerRank  #Solution  #Java 

Solution

  • Use BigInteger to calculate the sum and print first 10 characters by converting to string.
/* Solution to HackerRank: Large Sum
 * URL: https://www.hackerrank.com/contests/projecteuler/challenges/euler013
 */
import java.io.*;
import java.util.*;
import java.math.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int N = in.nextInt();
        
        BigInteger sum = new BigInteger("0");
        
        for(int t=0; t<N; t++){
            sum = sum.add(new BigInteger(in.next()));
        }
        
        System.out.println(sum.toString().substring(0, 10));
    }
}

HackerRank Contest - Project Euler - Power Digit Sum

#HackerRank  #Solution  #Java 

Solution

  • 2 to the power 1000 will be a huge number hence consider using BigInteger.
  • Recursively calculate the sum of all the digits.
/* Solution to HackerRank: Power Digit Sum
 * URL: https://www.hackerrank.com/contests/projecteuler/challenges/euler016
 */

import java.io.*;
import java.util.*;
import java.math.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        
        for(int t=0; t<T; t++){
            int N = in.nextInt();
            
            BigInteger base = new BigInteger("2");
            
            BigInteger pow = base.pow(N);
            
            System.out.println(digitSum(pow));
        }
    }
    
    public static BigInteger digitSum(BigInteger n){
        BigInteger ten = new BigInteger("10"); 
        
        if(n.compareTo(ten) == -1){
            // if number is less than 10 then it is reduced to single digit, hence return the digit
            return n;
        }
        else{            
            BigInteger r[] = n.divideAndRemainder(ten);
            
            // r[0] is the quotient and r[1] is the remainder
            return digitSum(r[0]).add(r[1]);
        }
    }
}

HackerEarth - Binary Tree

#HackerEarth  #Solution  #Java  #Binary Tree 

Solution

  • Diameter of a binary tree is maximum of diameter of current node, its left and right child.
/* Solution to HackerEarth: Binary Tree
 * URL: https://www.hackerearth.com/practice/data-structures/trees/binary-and-nary-trees/tutorial/
 */
import java.util.*;

class TestClass {
    public static void main(String args[] ) throws Exception {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        int X = in.nextInt();
        
        Node root = new Node(X);
        
        for(int t=0; t < T-1; t++){
            String path = in.next();
            
            Node node = new Node(in.nextInt());
            
            // add new node to the tree
            add(root, path.toCharArray(), 0, node);
        }
        
        System.out.println(diameter(root));
        
    }
    
    public static void add(Node root, char[] path, int current, Node target){
        if(path.length-1 == current){
            if(path[current] == 'L'){
                // update the value of temporary node or add the new node
                if(root.left != null){
                    root.left.value = target.value;
                }
                else{
                    root.left = target;
                }
            }
            else if(path[current] == 'R'){
                // update the value of temporary node or add the new node
                if(root.right != null){
                    root.right.value = target.value;
                }
                else{
                    root.right = target;
                }
            }
        }
        else{
            if(path[current] == 'L'){
                // add a temporary node if not added yet
                if(root.left == null){
                    root.left = new Node(0);
                }
                add(root.left, path, current+1, target);
            }
            else if(path[current] == 'R'){
                // add a temporary node if not added yet
                if(root.right == null){
                    root.right = new Node(0);
                }
                add(root.right, path, current+1, target);
            }
        }
    }
    
    public static int height(Node root){
        if(root == null){
            return 0;
        }
        else{
            return Math.max(height(root.left), height(root.right))+1;
        }
    }
    
    public static int diameter(Node root){
        if(root == null){
            return 0;
        }
        else{
            // diameter of current node
            int diameter = height(root.left)+height(root.right)+1;
            
            // return maximum of diameter of current node or left child or right child            
            return Math.max(diameter, Math.max(diameter(root.left),diameter(root.right)));
        }
    }
    
}

class Node{
    public int value;
    public Node left;
    public Node right;
    
    public Node(int value){
        this.value = value;
    }
}

HackerRank - Goodland Electricity

#HackerRank  #Solution  #Java 

Solution

  • Iterate through each city and check if it is already under range of previous tower.
  • If not, find a tower within the range to switch on.
/* Solution to HackerRank: Goodland Electricity
 * URL: https://www.hackerrank.com/challenges/pylons
 */
import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int N = in.nextInt();
        int K = in.nextInt();
        
        int[] cities = new int[N];
        
        for(int i=0; i < N; i++){
            cities[i] = in.nextInt();
        }
        
        int index = 0;
        int range = 0;
        int changes = 0;
        
        while(index < N){
            
            if(index < range){
                // city is already in range                
            }
            else{
                // find a tower to switch on
                
                int towerEnd = index+K;
                int towerStart = index-K+1;
                if(towerStart < 0){
                    towerStart = 0;
                }
                int tower = -1;
                
                for(int j=towerStart; j<towerEnd && j<N; j++){
                    if(cities[j] == 1){
                        tower = j;
                    }
                }
                
                // no way to handle current city
                if(tower == -1){
                    System.out.println(-1);
                    return;
                }
                else{
                    changes++;
                    index = tower;
                    range = index + K;
                }
            }
            
            index++;
        }
        
        System.out.println(changes);
    }
}

HackerRank - Max Min

#HackerRank  #Solution  #Java 

Solution

  • Sort the array of numbers
  • Find the minimum difference between ith and (i+K-1)th element in each iteration.
/* Solution to HackerRank: Max Min
 * URL: https://www.hackerrank.com/challenges/angry-children
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Solution {
    
   public static void main(String[] args) throws NumberFormatException, IOException {

    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(in.readLine());
    int K = Integer.parseInt(in.readLine());
    int[] list = new int[N];

    for(int i = 0; i < N; i ++)
        list[i] = Integer.parseInt(in.readLine());
      
    int unfairness = Integer.MAX_VALUE;
      
    Arrays.sort(list);

    // find minimum difference between ith and (i+K-1)th element in a sorted array
    for(int i = 0; i < N-K+1; i++){
        int diff = list[i+K-1] - list[i];
            
        unfairness = Math.min(unfairness, diff);
    }
      
    System.out.println(unfairness);
   }
}

HackerRank - Maximum Perimeter Triangle

#HackerRank  #Solution  #Java 

Solution

  • Iterate the sides in descending order
  • Check if sides make a triangle by checking if sum of two sides is greater than third side .
/* Solution to HackerRank: Maximum Perimeter Triangle
 * URL: https://www.hackerrank.com/challenges/maximum-perimeter-triangle
 */
import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int N = in.nextInt();
        
        int[] l = new int[N];
        
        for(int i=0; i < N; i++){
            l[i] = in.nextInt();
        }
        
        Arrays.sort(l);
        
        // iterate in descending order
        for(int a = l.length-1; a > 1; a--){
            for(int b = a-1; b > 0; b--){
                for(int c = b-1; c > -1; c--){
                    // check if sum of two sides is greater than the third side
                    if(l[a] + l[b] > l[c] && l[a] + l[c] > l[b] && l[b] + l[c] > l[a]){
                        System.out.println(l[c]+" "+l[b]+" "+l[a]);
                        return;
                    }
                }
            }
        }
        
        System.out.println(-1);
        
    }
}