**Problem:**

Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:

1. S(B) [≠] S(C); that is, sums of subsets cannot be equal.

2. If B contains more elements than C then S(B) [>] S(C).

For this problem we shall assume that a given set contains n strictly increasing elements and it already satisfies the second rule.

Surprisingly, out of the 25 possible subset pairs that can be obtained from a set for which n = 4, only 1 of these pairs need to be tested for equality (first rule). Similarly, when n = 7, only 70 out of the 966 subset pairs need to be tested.

For n = 12, how many of the 261625 subset pairs that can be obtained need to be tested for equality?

NOTE: This problem is related to problems 103 and 105.

1. S(B) [≠] S(C); that is, sums of subsets cannot be equal.

2. If B contains more elements than C then S(B) [>] S(C).

For this problem we shall assume that a given set contains n strictly increasing elements and it already satisfies the second rule.

Surprisingly, out of the 25 possible subset pairs that can be obtained from a set for which n = 4, only 1 of these pairs need to be tested for equality (first rule). Similarly, when n = 7, only 70 out of the 966 subset pairs need to be tested.

For n = 12, how many of the 261625 subset pairs that can be obtained need to be tested for equality?

NOTE: This problem is related to problems 103 and 105.

**Solution:**

25164150

**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 6

* By Nayuki Minase

*

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

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

*/

public final class p006 implements EulerSolution {

public static void main(String[] args) {

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

}

private static final int N = 100;

public String run() {

int sum = 0;

int sum2 = 0;

for (int i = 1; i <= N; i++) {

sum += i;

sum2 += i * i;

}

/*

* For the mathematically inclined:

* sum = N(N + 1) / 2.

* sum2 = N(N + 1)(2N + 1) / 6.

*/

return Integer.toString(sum * sum - sum2);

}

}

## No comments :

## Post a Comment