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:

$n = p_1^{e_1} * p_2^{e_2} * \ldots$

. To calculate the prime numbers I use for example Sieve of Eratosthenes. I calculate the exponents and product of calculated exponent values:

$divisors = \prod_{i=1}^{count~of~e} {e_i + 1}$

.
If there exists a number with

$divisors$

value greater than given amount, it is the result.

Prime factorization is used for calculating all divisors. For example

$6$

is divisible by

$2$

and

$3$

, so factorized

$6$

is:

$6 = 2^1 \times 3^1$

Let’s take for example the number

$24$

$24 = 2^3 \times 3^1$

All divisors of

$24$

are combinations of numbers when changing range of calculated exponent.There is

$2$

prime number to be combined from

$0$

$3$

exponent and

$3$

from

$0$

$1$

. These are the combinations:

1 = 2^0 * 3^0
2 = 2^1 * 3^0
3 = 2^0 * 3^1
4 = 2^2 * 3^0
6 = 2^1 * 3^1
8 = 2^3 * 3^0
12 = 2^2 * 3^1
24 = 2^3 * 3^1

1 = 2^0 * 3^0

2 = 2^1 * 3^0

3 = 2^0 * 3^1

4 = 2^2 * 3^0

6 = 2^1 * 3^1

8 = 2^3 * 3^0

12 = 2^2 * 3^1

24 = 2^3 * 3^1

There are

$8$

divisors for

$24$

– one exponent is

$3$

and second

$1$

. We can use

$0$

as an exponent, too. That’s why we have to multiply incremented exponent value.

$8 = (3 + 1) * (1 + 1)$

I created solution in:

Java

All solutions are also available on my GitHub profile.

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class HighlyDivisibleTriangularNumber
{
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		List<integer> primes = eratosthenes(10000000);

		int tests = Integer.parseInt(scanner.nextLine());
		for (int i = 0; i < tests; i++)
		{
			int num = 0;
			int div = 0;
			int divisors = Integer.parseInt(scanner.nextLine());
			outer: for (int number = 1; number < Integer.MAX_VALUE; number++)
			{
				int counter = 1;
				num += number;
				int n = num;
				for (int j = 0; j < primes.size() && div < n; j++)
				{
					div = primes.get(j);
					int exp = 0;
					while (n % div == 0)
					{
						exp++;
						n /= div;
					}
					counter *= (exp + 1);
					if (counter > divisors)
					{
						System.out.println(num);
						break outer;
					}
				}
			}
		}
		scanner.close();
	}

	private static List<integer> eratosthenes(int number)
	{
		boolean[] array = new boolean[number + 1];
		for (int i = 0; i < array.length; i++)
		{
			array[i] = true;
		}
		List<integer> primes = new ArrayList<integer>();
		for (int i = 2; i < array.length; i++)
		{
			if (array[i])
			{
				int j = i;
				while (i * j >= 0 && i * j < array.length)
				{
					array[i * j] = false;
					j++;
				}
				primes.add(i);
			}
		}
		return primes;
	}
}
</integer></integer></integer></integer>

import java.util.ArrayList;

import java.util.List;

import java.util.Scanner;

public class HighlyDivisibleTriangularNumber

{

public static void main(String[] args)

{

Scanner scanner = new Scanner(System.in);

List<integer> primes = eratosthenes(10000000);

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

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

{

int num = 0;

int div = 0;

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

outer: for (int number = 1; number < Integer.MAX_VALUE; number++)

{

int counter = 1;

num += number;

int n = num;

for (int j = 0; j < primes.size() && div < n; j++)

{

div = primes.get(j);

int exp = 0;

while (n % div == 0)

{

exp++;

n /= div;

}

counter *= (exp + 1);

if (counter > divisors)

{

System.out.println(num);

break outer;

}

scanner.close();

}

private static List<integer> eratosthenes(int number)

{

boolean[] array = new boolean[number + 1];

for (int i = 0; i < array.length; i++)

{

array[i] = true;

}

List<integer> primes = new ArrayList<integer>();

for (int i = 2; i < array.length; i++)

{

if (array[i])

{

int j = i;

while (i * j >= 0 && i * j < array.length)

{

array[i * j] = false;

j++;

}

primes.add(i);

}

return primes;

}

</integer></integer></integer></integer>

Pavol Pidanič

I can count to 1023 with 10 fingers

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

Hackerrank – Problem description

Solution

Java

Leave a Reply Cancel reply