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;