In this post i will explain my solution for a very nice mathematical problem. If you have an account on interviewstreet, you can view it using this link EQUATIONS. However in this problem you have the following equation (1/X) + (1/Y) = 1/N! and N is given, And you have to find all the valid pairs of X, and Y that solve this problem.

One can say that the simplest way is to iterate through all possible Xs, and Ys checking the pairs that solve the equation. But what if N is equal 10^6 for example?.

First lets define M = N!, then we have:

1x+1y=1N!=1M

Lets also define that X = M+a and Y = M+b. where (a, b) could be positive or negative numbers, then we have:

⇒2M+a+b(M+a)(M+b)=1M

We can solve the above equation and we will get the following:

2M2+M(a+b)=M2+M(a+b)+ab

⇒M2=ab

Now look at all the divisors ofM2=(N!)2 and find the values of a and b and hence find the values of x and y .

So we need to know how many divisors (N!)^2 have. As you may know that the number of divisors of a number equals the result of multiplying the exponents of the prime factors of this number.

So

So if we have n = a^x * b^y * c^z, where (a, b, c) are the prime factors of n, then the number of divisors of n = (x+1)*(y+1)*(z+1), I hear you asking why?

As you can see that all the divisors of n are multipliers of the prime factors of n.

So a could be chosen (x+1) times (0, 1, 2, ... x) times,

b could be chosen (y+1) times (0, 1, 2, .... y) times,

c could be chosen (z+1) times (0, 1, 2, ... z) times.

Now you have all the ideas that make a solution, show me your skills :)

One can say that the simplest way is to iterate through all possible Xs, and Ys checking the pairs that solve the equation. But what if N is equal 10^6 for example?.

First lets define M = N!, then we have:

Lets also define that X = M+a and Y = M+b. where (a, b) could be positive or negative numbers, then we have:

We can solve the above equation and we will get the following:

2M2+M(a+b)=M2+M(a+b)+ab

Now look at all the divisors of

So we need to know how many divisors (N!)^2 have. As you may know that the number of divisors of a number equals the result of multiplying the exponents of the prime factors of this number.

So if we have n = a^x * b^y * c^z, where (a, b, c) are the prime factors of n, then the number of divisors of n = (x+1)*(y+1)*(z+1), I hear you asking why?

As you can see that all the divisors of n are multipliers of the prime factors of n.

So a could be chosen (x+1) times (0, 1, 2, ... x) times,

b could be chosen (y+1) times (0, 1, 2, .... y) times,

c could be chosen (z+1) times (0, 1, 2, ... z) times.

Now you have all the ideas that make a solution, show me your skills :)

I think there is some problem in here.

ReplyDeleteWe are finding Y and X where Y,X >0

X=M+a; Y=M+b;

M^2=ab; so one of following will be happen

(a=b=M)

Y = X = 0;

OR

(a>M & b 0 & Y<0;

OR

(aM)

X<0 & Y>0;

in all the above cases both X & Y are never be > 0;