Posts for: #Solution

HackerRank Contest - Project Euler - Sum Square Difference

#HackerRank  #Solution  #Java 

Solution

  • Iterate from 1 to given number.
  • Add each iteration to sum and square of it to another sum.
  • Print absolute difference.
/* Solution to HackerRank: Sum Square Difference
 * URL: https://www.hackerrank.com/contests/projecteuler/challenges/euler006
 */
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 n = in.nextInt();
            
            long squareSum = 0;
            long sum = 0;
            
            for(int i = 1; i <= n; i++){
                squareSum+=(i*i);
                sum+=i;
            }
            
            System.out.println(Math.abs(sum*sum-squareSum));
        }
    }
}

HackerRank Contest - Project Euler - Largest Palindrome

#HackerRank  #Solution  #Java 

Solution

  • Iterate from the given number to zero.
  • Check if current iteration is a palindrome by using reverse() of StringBuilder class.
  • Check if current iteration is a product of two 3-digit numbers.
/* Solution to HackerRank: Largest Palindrome
 * URL: https://www.hackerrank.com/contests/projecteuler/challenges/euler004
 */
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 n = in.nextInt();
            
            // decrease n by 1 for first iteration, this will handle test case #3
            while(n-- > 0){
                if(isPalindrome(n) && isProduct(n)){
                    System.out.println(n);
                    break;
                }
            }
        }
    }
    
    static boolean isPalindrome(int n){
        String forward = Integer.toString(n);
        
        return new StringBuilder(forward).reverse().toString().equals(forward);
    }
    
    static boolean isProduct(int n){
        // set boundary value for a 3-digit number
        for(int i = 100; i < 1000; i++){
            // check if the other factor is a 3-digit number
            if(n%i == 0 && n/i > 99 && n/i < 1000){
                return true;
            }
        }
        
        return false;
    }
}

HackerRank Contest - Project Euler - Largest Prime Factor

#HackerRank  #Solution  #Java 

Solution

  • Find all the factors of the given number by iterating from 1 to square root of the number.
  • Sort all the factors in descending order and iterate to check if a factor is prime.
/* Solution to HackerRank: Largest Prime Factor
 * URL: https://www.hackerrank.com/contests/projecteuler/challenges/euler003
 */
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++){
            long n = in.nextLong();
            
            // get all the factors and sort is descending order
            List<Long> factors = getFactors(n);
            Collections.sort(factors, Collections.reverseOrder());
            
            for(Long factor: factors){
                if(isPrime(factor)){
                    System.out.println(factor);
                    break;
                }
            }
        }
    }
    
    static List<Long> getFactors(long n){
        List<Long> factors = new ArrayList<>();
        
        for(long i = 1; i <= Math.sqrt(n); i++){
            if(n%i == 0){
                factors.add(i);
                factors.add(n/i);
            }
        }
        
        return factors;
    }
    
    static boolean isPrime(long n){
        if(n%2 == 0){
            return false;
        }
        
        for(long i = 3; i <= Math.sqrt(n); i+=2){
            if(n%i == 0){
                return false;
            }
        }
        
        return true;
    }
}

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.