Posts for: #HackerRank

HackerRank Contest - HourRank 24 - Strong Password

#HackerRank  #Solution  #Java 

Solution

  • Count characters of each group in given string. Groups: digit, lower-case, upper-case and special characters
  • Add one of each group to the string if not already present i.e. count is 0.
  • Add required number of characters in case length of the string is less than 6.
/* Solution to HackerRank: Strong Password
 * URL: https://www.hackerrank.com/contests/hourrank-24/challenges/strong-password
 */
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    static int minimumNumber(int n, String password) {
        int digitCount = 0;
        int lowerCount = 0;
        int upperCount = 0;
        int specialCount = 0;
        
        int addCount = 0;
        
        for(char c : password.toCharArray()){
            if(Character.isDigit(c)){
                digitCount++;
            }
            else if(Character.isLowerCase(c)){
                lowerCount++;
            }
            else if(Character.isUpperCase(c)){
                upperCount++;
            }
            else{
                specialCount++;
            }
        }
        
        if(digitCount == 0){
            // add a digit
            addCount++;
            digitCount++;
        }
        
        if(lowerCount == 0){
            // add a lower case character
            addCount++;
            lowerCount++;
        }
        
        if(upperCount == 0){
            // add a lower case character
            addCount++;
            upperCount++;
        }
        
        if(specialCount == 0){
            // add a special character
            addCount++;
            specialCount++;
        }
        
        
        int total = digitCount + lowerCount + upperCount + specialCount;
        
        // check if total length is 6 or less
        if(total - 6 < 0){
            addCount += 6 - total;
        }
        
        return addCount;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String password = in.next();
        int answer = minimumNumber(n, password);
        System.out.println(answer);
        in.close();
    }
}

HackerRank - Journey to the Moon

#Graph Theory  #HackerRank  #Solution  #Java 

Solution

  • Graph is used to connect all astronauts to a country.
  • Each cluster of graph represents a country.
  • Each cluster is traversed to find the count of astronauts.
  • Number of possible combinations are calculated based on sizes of these countries.
/* Solution to HackerRank: Journey to the Moon
 * URL: https://www.hackerrank.com/challenges/journey-to-the-moon
 */

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();
        
        Graph graph = new Graph(N);
        
        int P = in.nextInt();
        
        for(int i = 0; i < P; i++){
            int source = in.nextInt();
            int destination = in.nextInt();
            
            graph.addEdge(source,destination);
        }
        
        
        boolean[] visited = new boolean[N];
        List<Integer> countries = new ArrayList<Integer>();
        long combinations = 0;

        // store size of each country by traversing each cluster
        for(int i = 0; i < N; i++){
            if(!visited[i]){
                countries.add(graph.dfs(i, visited));
            }
        }

        // calculating combinations with double caused test case #11 to timeout
        /*for(int i = 0; i < clusters.size()-1; i++){
            for (int j = i + 1; j < clusters.size(); j++){
                combinations += clusters.get(i) * clusters.get(j);
            }
        }*/
        
        /* Let size of each country be A, B, C, D ...
         * Combinations: AB + AC + AD + BC + BD + CD + ...
         * => AB + (A+B)C + (A+B+C)D
         */
        int sum = 0;
        for(int country : countries){
            combinations += sum*country;
            sum += country;    
        } 

        System.out.println(combinations);
    }
}
    
class Graph{
    List<Integer>[] vertices;
    
    public Graph(int count){
        vertices = new ArrayList[count];
        
        for(int i = 0; i < count; i++){
            vertices[i] = new ArrayList<Integer>();
        }
    }
    
    public void addEdge(int source, int destination){
        vertices[source].add(destination);
        vertices[destination].add(source);
    }
    
    // modified DFS to return number of vertices traversed
    public int dfs(int source, boolean[] visited){
        visited[source] = true;
        int count = 1;
        
        for(Integer vertex: vertices[source]){
            if(!visited[vertex]){
                count += dfs(vertex, visited);
            }
        }
        
        return count;
    }
}

HackerRank - Roads and Libraries

#Graph Theory  #HackerRank  #Solution  #Java 

Minimum Cost

  • If the number of roads is zero or cost of building a road is more than cost of building a library, then building libraries in each of the cities will result in minimum cost.
  • If the cost of building a library is less than cost of building a road, then building a single library and building roads to connected cities will result in minimum cost.

Clusters

There can be few set of cities that are not connected to each other and are clusters. Minimum cost is summation of minimum cost for all clusters.