Posts for: #Solution

HackerRank Contest - Regular Expresso - Winning Tic Tac Toe

#HackerRank  #Solution  #Regular Expression 

Solution

/* Solution to HackerRank: Winning Tic Tac Toe
 * URL: https://www.hackerrank.com/contests/regular-expresso/challenges/winning-tic-tac-toe
 */

"(X|O)((...\\1){2}|..\\1..\\1|.\\1.\\1..$|\\1\\1(...)*$)"

Case 1

(...\\1){2}) or (...\\1...\\1)

will take care of

X O -
O X O
- - X

Case 2

(..\\1..\\1)

will take care of 

X - O
X O -
X - O

OR 

- X O
O X -
- X O

OR

- O X
O - X
- O X

Case 3

(.\\1.\\1..$)

will take care of 

O - X
- X O
X O -

false positive if ..$ is not included

O X -
X O X
- O X

Case 4

(\\1\\1(...)*$)

will take care of 

X X X
O - O
- - -

OR 

O - O
X X X
O - -

OR

O - -
O - X
X X X

false positive if (...)*$ is not included

O - X
X X -
- O O

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

HackerEarth - Mirror Image

#HackerEarth  #Solution  #Java  #Binary Tree 

Solution

  • Parse input and build the tree by maintaining an index HashMap.
  • Traverse tree and mirror tree simultaneously to find the mirror node.
/* Solution to HackerEarth: Mirror Image
 * URL: https://www.hackerearth.com/practice/data-structures/trees/binary-and-nary-trees/practice-problems/algorithm/mirror-image-2/
 */
import java.util.*;

class TestClass {
    public static void main(String args[] ) throws Exception {
        //Scanner
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int Q = in.nextInt();
        
        Map<Integer, Node> index = new HashMap<>();
        
        // initialize root node
        Node root = new Node(1);
        
        index.put(1, root);
        
        // build tree
        for(int i=0; i < N-1; i++){
            int parent = in.nextInt();
            int child = in.nextInt();
            char side = in.next().charAt(0);
            
            // get parent node from index
            Node node = index.get(parent);
            
            // create a new child node and add to index
            Node childNode = new Node(child);
            index.put(child, childNode);
            
            if(side == 'L'){
                node.left = childNode;
            }
            else if (side == 'R'){
                node.right = childNode;
            }
        }
        
        // process queries
        for(int i=0; i < Q; i++){
            int target = in.nextInt();
            
            System.out.println(findMirror(root, target));
        }

    }
    
    public static int findMirror(Node root, int target){
        if(root.value == target){
            return target;
        }
        else{
            return recurse(target, root.left, root.right);
        }
    }
    
    public static int recurse(int target, Node left, Node right){

        // no need to further traverse because either current node or mirror node is null
        if(left == null || right == null){
            return -1;
        }
        
        // if target found return mirror node
        if(left.value == target){
            return right.value;
        }
        
        if(right.value == target){
            return left.value;
        }
        
        int mirror = recurse(target, left.left, right.right);
        
        // return mirror if found
        if(mirror > 0){
            return mirror;
        }
        
        return recurse(target, left.right, right.left);
    }
    
    
}

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

HackerRank - Largest Permutation

#HackerRank  #Solution  #Java 

Solution #1

  • Keep indexes of all numbers in a HashMap.
  • Check if current maximum number is already at desired index i.e highest at index 0, second highest at index 1 and so on.
  • If not, keep on swapping them till all the swaps are exhausted.
/* Solution to HackerRank: Largest Permutation
 * URL: https://www.hackerrank.com/challenges/largest-permutation
 */
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[] n = new int[N];
        
        Map<Integer,Integer> index = new HashMap<>();
        
        for(int i = 0; i < N; i++){
            n[i] = in.nextInt();
            
            index.put(n[i],i);
        }
        
        int max = N;
        
        for(int j = 0; j < N ; j++){
            
            int maxIndex = index.get(max);
            
            if(maxIndex != j){
                // make a swap
                K--;
                
                int temp = n[j];
                n[j] = max;
                n[maxIndex] = temp;
                
                // update indexes
                index.put(max,j);
                index.put(temp,maxIndex);
            }
            
            max--;
            
            // break the loop if swaps are exhausted
            if(K == 0){
                break;
            }
        }
        
        for(int i = 0; i < N; i++){
            System.out.print(n[i] + " ");
        }
        
    }
}

Solution #2

  • Find the maximum number in each iteration.
  • Swap them in order of decreasing value till all the swaps are exhausted.

Test cases 13 to 15 timed out for this solution.

HackerRank - Hackerland Radio Transmitters

#HackerRank  #Solution  #Java 

Solution

  • Iterate through each house in a sorted order.
  • Check if current house is in range of last transmitter.
  • If not, find a house to put transmitter on so that current house is in range.
/* Solution to HackerRank: Hackerland Radio Transmitters
 * URL: https://www.hackerrank.com/challenges/hackerland-radio-transmitters
 */
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 in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] x = new int[n];
        for(int x_i=0; x_i < n; x_i++){
            x[x_i] = in.nextInt();
        }
        
        Arrays.sort(x);
        
        int i = 0;
        int range = 0;
        int count = 0;
        
        while(i < n){
            
            if(x[i] < range){
                // current house is already in range of last transmitter
            }
            else{
                count++;

                // check where can the transmitter be placed
                int j = x[i] + k;
                int l = i;

                // transmitter can not be placed farther than j to cover current house,
                // check for the last house within j
                while(l < n && x[l] <= j){
                    l++;
                }
                
                // transmitter is placed at l-1 house
                range = x[--l] + k + 1;
                
                // move counter to l as houses till l are already in range of new transmitter
                i = l;
            }
            
            i++;
        }
        
        System.out.println(count);
    }
}

HackerRank - Minimum Loss

#HackerRank  #Solution  #Java 

Solution #1

  • Keep prices and corresponding index in a HashMap.
  • Sort the prices array in ascending order so that combination of minimum difference can be found by comparing adjacent prices.
  • Check that the indexes buying and selling are in correct order so that year of buying is less than year of selling.
/* Solution to HackerRank: Minimum Loss
 * URL: https://www.hackerrank.com/challenges/minimum-loss
 */
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();
        long[] p = new long[n];
        
        Map<Long,Integer> index = new HashMap<>();
        
        for(int i=0; i < n; i++){
            p[i] = in.nextLong();
            index.put(p[i], i);
        }
        
        Arrays.sort(p);
        
        long min = Long.MAX_VALUE;
        
        for(int i=0; i < n-1; i++){
            if(p[i+1] - p[i] < min && index.get(p[i+1]) < index.get(p[i])){
                min = p[i+1] - p[i];
            }
        }
        
        System.out.println(min);
    }
}

Solution #2

  • Compare each possible combination to determine the minimum difference.

Test cases 11 to 15 timed out for below solution.

HackerRank Contest - HourRank 24 - Mutual Indivisibility

#HackerRank  #Solution  #Java 

Solution

  • Start iterating numbers from b to a because combination of larger numbers are more likely to be indivisible.
  • Keep an array representing all numbers including a and b.
  • Strike out multiples of current number from array in each iteration.
/* Solution to HackerRank: Mutual Indivisibility
 * URL: https://www.hackerrank.com/contests/hourrank-24/challenges/mutual-indivisibility
 */
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 in = new Scanner(System.in);
        int t = in.nextInt();
        for(int a0 = 0; a0 < t; a0++){
            int a = in.nextInt();
            int b = in.nextInt();
            int x = in.nextInt();
            
            int[] skills =  new int[b-a+1];
            
            int teamSize = 0;
            
            for(int i=b; i>=a; i--){
                teamSize++;
                    
                int multiple = i*2;
                int count = 2;

                while(multiple <= b){
                    // strike out the multiple, hence decrease team size
                    skills[multiple-a] = 1;
                    teamSize--;

                    count++;
                    multiple = i*count;
                }
                
                // break as needed team size is reached
                if(teamSize == x){
                    break;
                }
            }        
            
            
            if(teamSize >= x){
                int i = skills.length-1;
                
                while(i >= 0 && x > 0){
                   if(skills[i] == 0){
                       System.out.print(i+a);
                       System.out.print(" ");
                       x--;
                   }
                   i--;
                }
                
                System.out.println("");
            }
            else{
                System.out.println(-1);
            }
            
        }
        in.close();
    }
}