Ok, you didn't explain the limits on your "integers", so I am going to
go ahead and do the cheaters algorithm. Compute each of the following
(which are each O(n)):
1. s = sum of numbers given.
2. p = product of numbers given.
3. t = n!
Then if the two numbers are a and b, we know that:
1. (a + b) = n*(n+1)/2 - s
2. (a*b) = t / p
Now we can see that:
(x - a) * (x - b) = x^2 - (a + b) * x + (a * b)
However this quadratic clearly has the roots a and b. So solving for
the two roots using the classical quadratic formula will yield the two
solutions a and b. QED.
Ok, but all this requires a bignum library and n! is actually a very
large and slow number to compute (that requires roughly O(n*log(n))
memory).
It's OK if the array is small.
/* BEGIN no_extra_space.c */
#include <stdio.h>
#define NMEMB 10
#define FIRST_ZERO 3
#define SECOND_ZERO 8
#define LU_RAND(S) ((S) * 69069 + 362437)
#define LU_RAND_SEED 123456789LU
void all_different(long unsigned *array, long unsigned n,
long unsigned seed);
void place_zeros(long unsigned *array, long unsigned n,
long unsigned first, long unsigned second);
void find_numbers(long unsigned *array, long unsigned n,
long unsigned *number);
long unsigned irt(long unsigned n);
int main(void)
{
long unsigned array[NMEMB], number[2], n;
all_different(array, NMEMB, LU_RAND_SEED);
place_zeros(array, NMEMB, FIRST_ZERO, SECOND_ZERO);
find_numbers(array, NMEMB, number);
for (n = 0; n != NMEMB; ++n) {
printf("%lu\n", array[n]); }
printf("\n%lu %lu\n", number[0], number[1]);
return 0;
}
void find_numbers(long unsigned *array, long unsigned n,
long unsigned *number)
{
const size_t count = n;
long unsigned n_factorial, n_sum;
long unsigned array_factorial, array_sum;
long unsigned product, sum;
for (n_factorial = 1; n != 0; --n) {
n_factorial *= n;
}
n = count;
for (n_sum = 0; n != 0; --n) {
n_sum += n;
}
array_factorial = 1;
n = count;
while (n-- != 0) {
if (array[n] != 0) {
array_factorial *= array[n];
}
}
n = count;
array_sum = 0;
while (n-- != 0) {
array_sum += array[n];
}
product = n_factorial / array_factorial;
sum = n_sum - array_sum;
number[0] = (sum - irt(sum * sum - 4 * product)) / 2;
number[1] = sum - number[0];
}
void place_zeros(long unsigned *array, long unsigned n,
long unsigned first, long unsigned second)
{
while (n-- != 0) {
if (array[n] == first || array[n] == second) {
array[n] = 0;
}
}
}
void all_different(long unsigned *array,
long unsigned n, long unsigned seed)
{
long unsigned i, r;
array[0] = 1;
for (i = 1; n > i; ++i) {
seed = LU_RAND(seed);
r = seed % (i + 1);
array
= 0;
array = array[r];
array[r] = i + 1;
}
}
long unsigned irt(long unsigned n)
{
long unsigned a, b;
a = n;
for (b = (1 == n) + n >> 1; n > b; b = a / n + n >> 1) {
n = b;
}
return n;
}
/* END no_extra_space.c */
