Interview Question
Country: India
First, it is easy to show that there are no 2 solutions with the same x (the same holds for y because the problem is symmetric).
Indeed, suppose, we have 2 solutions (x0, y1) and (x0, y2), then:
(x0 + y1) * n! = x0 * y1
(x0 + y2) * n! = x0 * y2
from where it follows that y1 == y2.
Next, since the problem is symmetric in x and y, we can limit our search space
until we reach a "crossover" point, where x becomes equal to y.
From the original equation, we can easily find that this happens when: x = y = 2n!
Hence, the algorithm is as follows: iterate x from 0 to 2n! and count the solutions, then do the same for y. In fact, we do not need to iterate for y separately, because the # of solutions will be the same but I did it for demonstration purposes:
void count_solutions() {
int c = 0; // solution counter
int n_fact = 120; // this is n!
for(int x = 0; x <= n_fact*2; x++) {
int y = (x == n_fact ? 1 : x*n_fact / (x-n_fact));
if(y*n_fact == x*(y-n_fact))
printf("%d: %d %d\n", ++c, x, y);
}
for(int y = 1; y < n_fact*2; y++) {
int x = (y == n_fact ? 1 : y*n_fact / (y-n_fact));
if(x*n_fact == y*(x-n_fact))
printf("%d: %d %d\n", ++c, x, y);
}
printf("# of solutions found: %d\n", c);
}
is this work?
- Anonymous April 28, 2012void fun(int n)
{
if(n < 0)
return;
else if(n == 0)
n = 1;
else
{
for (int i = n-1; i >=1; i--) {
n *= i;
}
}
for(int x = 1; x <= n*2; x++)
for (int y = 1; y <= n*2; y++) {
if((x*y)%(x+y)==0)
{
if(x*y/(x+y)==n)
{
std::cout<<"x:" << x << " y: "<< y<< std::endl;
}
}
}
}