Pavol Pidanič

Hackerrank – Project Euler+ #016 – Power digit sum

Hackerrank – Problem description The problem description – Hackerrank. Solution The catch is to use a feature of chosen programming language, which allows us operation with big numbers (e. g. BigInteger in Java) I created solution in: Java All solutions are also available on my GitHub profile. Java

import java.math.BigInteger;
import java.util.Scanner;

public class PowerDigitSum
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int tests = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < tests; i++)
        {
            BigInteger base = new BigInteger("2");
            int exp = Integer.parseInt(scanner.nextLine().trim());
            base = base.pow(exp);
            long result = sumDigits(base);
            System.out.println(result);
        }
        scanner.close();
    }

    private static long sumDigits(BigInteger num)
    {
        long result = 0;
        char[] digits = num.toString().toCharArray();
        for (char digit : digits)
        {
            result += Character.digit(digit, 10);
        }
        return result;
    }
}

import java.math.BigInteger;

import java.util.Scanner;

public class PowerDigitSum

{

public static void main(String[] args)

{

Scanner scanner = new Scanner(System.in);

int tests = Integer.parseInt(scanner.nextLine());

for (int i = 0; i < tests; i++)

{

BigInteger base = new BigInteger("2");

int exp = Integer.parseInt(scanner.nextLine().trim());

base = base.pow(exp);

long result = sumDigits(base);

System.out.println(result);

}

scanner.close();

}

private static long sumDigits(BigInteger num)

{

long result = 0;

char[] digits = num.toString().toCharArray();

for (char digit : digits)

{

result += Character.digit(digit, 10);

}

return result;

}

Hackerrank – Project Euler+ #015 – Lattice paths

Hackerrank – Problem description The problem description – Hackerrank. Solution The solution is based on this article. I created solution in: Java All solutions are also available on my GitHub profile. Java

import java.math.BigInteger;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class LatticePaths
{
    // http://www.robertdickau.com/lattices.html
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int tests = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < tests; i++)
        {
            String[] numbers = scanner.nextLine().split("\\s+");
            int n = Integer.parseInt(numbers[0]);
            int m = Integer.parseInt(numbers[1]);
            Set<Integer> nFactorialMembers = new HashSet<>();
            for (int j = 1; j <= n; j++)
            {
                nFactorialMembers.add(j);
            }
            Set<Integer> mFactorialMembers = new HashSet<>();
            for (int j = 1; j <= m; j++)
            {
                mFactorialMembers.add(j);
            }
            Set<Integer> mnFactorialMembers = new HashSet<>();
            for (int j = 1; j <= m + n; j++)
            {
                mnFactorialMembers.add(j);
            }
            // (m+n) chose m === (m+n)!/m!n!
            // divided n!
            mnFactorialMembers.removeAll(nFactorialMembers);

            BigInteger result = BigInteger.ONE;
            for (Integer k : mnFactorialMembers)
            {
                result = result.multiply(new BigInteger(k.toString()));
            }
            for (Integer k : mFactorialMembers)
            {
                result = result.divide(new BigInteger(k.toString()));
            }
            System.out.println(result.mod(new BigInteger("1000000007")));
        }
        scanner.close();
    }
}

import java.math.BigInteger;

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

public class LatticePaths

{

// http://www.robertdickau.com/lattices.html

public static void main(String[] args)

{

Scanner scanner = new Scanner(System.in);

int tests = Integer.parseInt(scanner.nextLine());

for (int i = 0; i < tests; i++)

{

String[] numbers = scanner.nextLine().split("\\s+");

int n = Integer.parseInt(numbers[0]);

int m = Integer.parseInt(numbers[1]);

Set<Integer> nFactorialMembers = new HashSet<>();

for (int j = 1; j <= n; j++)

{

nFactorialMembers.add(j);

}

Set<Integer> mFactorialMembers = new HashSet<>();

for (int j = 1; j <= m; j++)

{

mFactorialMembers.add(j);

}

Set<Integer> mnFactorialMembers = new HashSet<>();

for (int j = 1; j <= m + n; j++)

{

mnFactorialMembers.add(j);

}

// (m+n) chose m === (m+n)!/m!n!

// divided n!

mnFactorialMembers.removeAll(nFactorialMembers);

BigInteger result = BigInteger.ONE;

for (Integer k : mnFactorialMembers)

{

result = result.multiply(new BigInteger(k.toString()));

}

for (Integer k : mFactorialMembers)

{

result = result.divide(new BigInteger(k.toString()));

}

System.out.println(result.mod(new BigInteger("1000000007")));

}

scanner.close();

}

Hackerrank – Project Euler+ #014 – Longest Collatz sequence

Hackerrank – Problem description The problem description – Hackerrank. Solution There are given 2 rules for Collatz sequence: if n is even, then n/2 if n is odd, then 3n + 1 The given problem set of possibilities is to big and it would take too much time. My solution is to precalculate sequence values […]

Hackerrank – Project Euler+ #013 – Large sum

Hackerrank – Problem description The problem description – Hackerrank. Solution We need to sum all given numbers. The catch is to use a feature of chosen programming language, which allows us operation with big numbers (e. g. BigInteger in Java) I created solution in: Java All solutions are also available on my GitHub profile. Java […]

Hackerrank – Project Euler+ #012 – Highly divisible triangular number

Hackerrank – Problem description The problem description – Hackerrank. Solution I check all numbers from 1 to N. I need to do a prime factorization of each number. In the end there is a following state: . To calculate the prime numbers I use for example Sieve of Eratosthenes. I calculate the exponents […]

Hackerrank – Project Euler+ #011 – Largest product in a grid

Hackerrank – Problem description The problem description – Hackerrank. Solution We have to calculate products of number foursomes for all directions in a grid and take the greatest product value. I created solution in: Java All solutions are also available on my GitHub profile. Java

import java.util.Scanner;

public class LargestProductGrid
{
	private static final int N = 20;

	private static final int ADJACENT = 4;

	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		int[][] visited = new int[N][N];
		int[][] matrix = new int[N][N];
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				matrix[i][j] = scanner.nextInt();
			}
		}
		System.out.println(max(matrix, visited));

		scanner.close();
	}

	private static long max(int[][] matrix, int[][] visited)
	{
		long max = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				long product = productToRight(matrix, i, j);
				if (product > max)
				{
					max = product;
				}

				product = productToDown(matrix, i, j);
				if (product > max)
				{
					max = product;
				}

				product = productToDiagRight(matrix, i, j);
				if (product > max)
				{
					max = product;
				}

				product = productToDiagLeft(matrix, i, j);
				if (product > max)
				{
					max = product;
				}
			}
		}

		return max;
	}

	private static long productToRight(int[][] matrix, int i, int j)
	{
		long product = 1;
		if (j <= N - ADJACENT)
		{
			for (int r = j; r < j + ADJACENT; r++)
			{
				product *= matrix[i][r];
			}
		}
		return product;
	}

	private static long productToDown(int[][] matrix, int i, int j)
	{
		long product = 1;
		if (i <= N - ADJACENT)
		{
			for (int r = i; r < i + ADJACENT; r++)
			{
				product *= matrix[r][j];
			}
		}
		return product;
	}

	private static long productToDiagRight(int[][] matrix, int i, int j)
	{
		long product = 1;
		int s = j;
		if (i <= N - ADJACENT && j <= N - ADJACENT)
		{
			for (int r = i; r < i + ADJACENT; r++)
			{
				product *= matrix[r][s++];
			}
		}
		return product;
	}

	private static long productToDiagLeft(int[][] matrix, int i, int j)
	{
		long product = 1;
		if (i <= N - ADJACENT && j >= ADJACENT - 1)
		{
			for (int r = i; r < i + ADJACENT; r++)
			{
				product *= matrix[r][j--];
			}
		}
		return product;
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

import java.util.Scanner;

public class LargestProductGrid

{

private static final int N = 20;

private static final int ADJACENT = 4;

public static void main(String[] args)

{

Scanner scanner = new Scanner(System.in);

int[][] visited = new int[N][N];

int[][] matrix = new int[N][N];

for (int i = 0; i < N; i++)

{

for (int j = 0; j < N; j++)

{

matrix[i][j] = scanner.nextInt();

}

System.out.println(max(matrix, visited));

scanner.close();

}

private static long max(int[][] matrix, int[][] visited)

{

long max = 0;

for (int i = 0; i < N; i++)

{

for (int j = 0; j < N; j++)

{

long product = productToRight(matrix, i, j);

if (product > max)

{

max = product;

}

product = productToDown(matrix, i, j);

if (product > max)

{

max = product;

}

product = productToDiagRight(matrix, i, j);

if (product > max)

{

max = product;

}

product = productToDiagLeft(matrix, i, j);

if (product > max)

{

max = product;

}

return max;

}

private static long productToRight(int[][] matrix, int i, int j)

{

long product = 1;

if (j <= N - ADJACENT)

{

for (int r = j; r < j + ADJACENT; r++)

{

product *= matrix[i][r];

}

return product;

}

private static long productToDown(int[][] matrix, int i, int j)

{

long product = 1;

if (i <= N - ADJACENT)

{

for (int r = i; r < i + ADJACENT; r++)

{

product *= matrix[r][j];

}

return product;

}

private static long productToDiagRight(int[][] matrix, int i, int j)

{

long product = 1;

int s = j;

if (i <= N - ADJACENT && j <= N - ADJACENT)

{

for (int r = i; r < i + ADJACENT; r++)

{

product *= matrix[r][s++];

}

return product;

}

private static long productToDiagLeft(int[][] matrix, int i, int j)

{

long product = 1;

if (i <= N - ADJACENT && j >= ADJACENT - 1)

{

for (int r = i; r < i + ADJACENT; r++)

{

product *= matrix[r][j--];

}

return product;

}

Hackerrank – Project Euler+ #010 – Summation of primes

Hackerrank – Problem description The problem description – Hackerrank. Solution First, I created a list of all prime numbers from 2 to 106 (upper constraint). I used Sieve of Eratosthenes algorithm. Then, I sum each element from a subset of prime numbers gained from test case. I created solution in: Java All solutions are also […]

Hackerrank – Project Euler+ #009 – Special Pythagorean triplet

Hackerrank – Problem description The problem description – Hackerrank. Solution I found the solution on StackOverflow. One could use the Wikipedia as a source. I created solution in: Java All solutions are also available on my GitHub profile. Java

import java.util.Scanner;

public class PythagoreanTriplet
{
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		int tests = scanner.nextInt();
		for (int i = 0; i < tests; i++)
		{
			int n = scanner.nextInt();
			System.out.println(findTripletDirty(n));
		}
		scanner.close();
	}

	static long findTriplet(int number)
	{
		long maxTriplet = -1;
		for (int a = 1; a <= number / 3; a++)
		{
			int aSquare = a * a;
			for (int b = a + 1; b <= number / 2; b++)
			{
				int c = number - a - b;
				if(c > 0 && c * c == aSquare + b * b)
				{
					long product = (long) a * b * c;
					if(product > maxTriplet)
					{
						maxTriplet = product;
					}
				}
			}
		}
		return maxTriplet;
	}

	// http://stackoverflow.com/questions/2817848/find-pythagorean-triplet-for-which-a-b-c-1000
	static long findTripletDirty(int number)
	{
		long max = -1;
		// sum of integer Pythagorean triplet is always even
		if(number % 2 == 0)
		{
			for (int b = 1; b < number / 2; b++)
			{
				if(number * (number / 2 - b) % (number - b) == 0)
				{
					int a = number * (number / 2 - b) / (number - b);
					int c = number - a - b;
					long product = (long) c * a * b;
					if(product > max)
					{
						max = product;
					}
				}
			}
		}
		return max;
	}
}

import java.util.Scanner;

public class PythagoreanTriplet

{

public static void main(String[] args)

{

Scanner scanner = new Scanner(System.in);

int tests = scanner.nextInt();

for (int i = 0; i < tests; i++)

{

int n = scanner.nextInt();

System.out.println(findTripletDirty(n));

}

scanner.close();

}

static long findTriplet(int number)

{

long maxTriplet = -1;

for (int a = 1; a <= number / 3; a++)

{

int aSquare = a * a;

for (int b = a + 1; b <= number / 2; b++)

{

int c = number - a - b;

if(c > 0 && c * c == aSquare + b * b)

{

long product = (long) a * b * c;

if(product > maxTriplet)

{

maxTriplet = product;

}

return maxTriplet;

}

// http://stackoverflow.com/questions/2817848/find-pythagorean-triplet-for-which-a-b-c-1000

static long findTripletDirty(int number)

{

long max = -1;

// sum of integer Pythagorean triplet is always even

if(number % 2 == 0)

{

for (int b = 1; b < number / 2; b++)

{

if(number * (number / 2 - b) % (number - b) == 0)

{

int a = number * (number / 2 - b) / (number - b);

int c = number - a - b;

long product = (long) c * a * b;

if(product > max)

{

max = product;

}

return max;

}

Hackerrank – Project Euler+ #008 – Largest product in a series

Hackerrank – Problem description The problem description – Hackerrank. Solution I took k following numbers and I calculate a product of these k numbers. Compare the product with actual maximum. Print the maximum if there are no more k following numbers. I created solution in: Java All solutions are also available on my GitHub profile. […]

Hackerrank – Project Euler+ #007 – 10001st prime

Hackerrank – Problem description The problem description – Hackerrank. Solution The challenge has upper constraint that we could have at most 10 001 prime numbers from the smallest (2). I found out that the upper bound is the number 104 743. There exist first 10 001 prime numbers. We calculate list all of them and […]