Posts for: #Solution

LeetCode - Rank Teams by Votes

#LeetCode  #Solution  #JavaScript 

Solution to LeetCode: Rank Teams by Votes

Solution

  • Use a map of arrays (2 dimensional data structure) to accumulate the vote counts per position per team
  • Sort the map based on the vote counts per position and team name
/* Solution to LeetCode: Rank Teams by Votes
 * URL: https://leetcode.com/problems/rank-teams-by-votes/
 */

const rankTeams = (votes) => {
    // map to hold vote count per team
    const rankings = new Map()

    // loop through each vote
    for (const vote of votes) {
        //console.log(vote)

        // loop through each team position in a vote
        for (let position = 0; position < vote.length; position++) {
            const team = vote[position]

            // update the vote count for the team at the position
            let ranking = rankings.get(team)

            // create an empty array, if not already
            if (!ranking) ranking = new Array(vote.length).fill(0)

            // record the vote
            ranking[position]++

            // console.log(team, ranking)
            rankings.set(team, ranking)
        }
    }

    // sort the teams based on the votes
    const sorted = [...rankings].sort((a, b) => {
        const rankingA = a[1]
        const rankingB = b[1]

        for (let position = 0; position < rankingA.length; position++) {
            // if vote count is same, check for next position
            if (rankingA[position] == rankingB[position]) continue

            // return team with highest vote count
            else return rankingB[position] - rankingA[position]
        }

        // break tie based on team name
        return a[0] - b[0]
    })

    // join the sorted teams
    const result = sorted.map((ranking) => ranking[0]).join('')

    // console.log(result)

    return result

}

// test case
console.assert(rankTeams(["ABC", "ACB", "ABC", "ACB", "ACB"]) === 'ACB')

// test case
console.assert(rankTeams(["WXYZ","XYZW"]) === 'XWYZ')

// test case
console.assert(rankTeams(["ZMNAGUEDSJYLBOPHRQICWFXTVK"]) === 'ZMNAGUEDSJYLBOPHRQICWFXTVK')

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