**Problem:**

By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, [−], *, /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

8 = (4 * (1 + 3)) / 2

14 = 4 * (3 + 1 / 2)

19 = 4 * (2 + 3) [−] 1

36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a [<] b < c [<] d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

For example,

8 = (4 * (1 + 3)) / 2

14 = 4 * (3 + 1 / 2)

19 = 4 * (2 + 3) [−] 1

36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a [<] b < c [<] d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

**Solution:**

16695334890

**Code:**

The solution may include methods that will be found here: Library.java .

The solution may include methods that will be found here: Library.java .

public interface EulerSolution{

public String run();

}

/*

* Solution to Project Euler problem 43

* By Nayuki Minase

*

* http://nayuki.eigenstate.org/page/project-euler-solutions

* https://github.com/nayuki/Project-Euler-solutions

*/

public final class p043 implements EulerSolution {

public static void main(String[] args) {

System.out.println(new p043().run());

}

private static int[] DIVISIBILITY_TESTS = {2, 3, 5, 7, 11, 13, 17}; // First 7 primes

public String run() {

long sum = 0;

int[] digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

outer:

do {

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

if (toInteger(digits, i + 1, 3) % DIVISIBILITY_TESTS[i] != 0)

continue outer;

}

sum += toInteger(digits, 0, digits.length);

} while (Library.nextPermutation(digits));

return Long.toString(sum);

}

private static long toInteger(int[] digits, int off, int len) {

long result = 0;

for (int i = off; i < off + len; i++)

result = result * 10 + digits[i];

return result;

}

}

## No comments :

## Post a Comment