Solution
- Iterate from 2 to the given number. Consider odd numbers only except 2.
- Check each iteration for prime number.
However, Test case 4 timed out for below solution.
HackerRank Contest - Project Euler - Sum Square Difference
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
Solution
- Iterate from the given number to zero.
- Check if current iteration is a palindrome by using
reverse()ofStringBuilderclass. - 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
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 - Project Euler - Even Fibonacci Numbers
Solution #1
Test cases 2,3 timed out for below solution.
HackerRank Contest - HourRank 24 - Strong Password
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
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
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.