Mike Lewis
BAN USERIf you wanted to get real tricky and not use an extra array or a second loop:
int[] numbers = {3, 2, 4, 8, 10, 9, 1, 6};
int sum = 0;
int product = 1;
for (int i = 0; i < 8; i++) {
sum += numbers[i];
product *= numbers[i];
}
int missingSum = 55 - sum;
int missingProduct = 3628800 / product;
int root = (int) (Math.sqrt(missingSum * missingSum - 4 * missingProduct));
System.out.println (((missingSum - root) / 2) + ", " + ((missingSum + root) / 2));
quick explanation:
let the missing numbers be x and y
x + y = missingSum
x * y = missingProduct
multiply both sides of the first equation by y
x * y + y^2 = y * missingSum
now replace in missingProduct and move the right side of the equation to the left and rearrange a little:
y^2 - y * missingSum + missingProduct = 0
this is a quadratic equation, so you can use the quadratic formula, where a = 1, b = -missingSum, c = missingProduct.
If you're trying to find duplicates in an infinite quantity of numbers with infinite range and you can only use a boolean array of finite size, you're going to have a hard time.
If you're allowed to have some small number of errors, I believe the traditional solution for this kind of problem is to use a Bloom filter.
eh? I used int, not short. MAXINT is 2,147,483,647.
- Mike Lewis September 08, 2013