Caution: This is a spoiler with complete solution. Do not read further if you haven't tried it yet.
Abbreviated problem definition: Given a fraction 1/z, it can be represented as 1/x + 1/y where x >=y. Find all combinations for a given 0 < z <= 10000.
Sample Inputs:
2
12
Sample Outputs:
2 --# of solutions
1/2 = 1/6 + 1/3
1/2 = 1/4 + 1/4
8 --# of solutions
1/12 = 1/156 + 1/13
1/12 = 1/84 + 1/14
1/12 = 1/60 + 1/15
1/12 = 1/48 + 1/16
1/12 = 1/36 + 1/18
1/12 = 1/30 + 1/20
1/12 = 1/28 + 1/21
1/12 = 1/24 + 1/24
Expression:
1/z = 1/x + 1/y
1/z = (y + x)/ (x * y)
z = (x * y)/(x + y) --(1)
z * (x + y) = (x * y)
z * x + z * y = y * x
z * y = (y - z) * x
x = (z * y) / (y - z) --(2)
Looking at the pattern for the samples, we decrease y and find the x,
if possible.
Start with y = 2 * z = 2 * 2 = 4:
1/2 = 1/4 + 1/4
2 = (4 * 4)/(4 + 4) --using (1) above.
Try y = 3;
2 = (x * 3)/ (x + 3)
2 * (x + 3) = x * 3
2*x + 6 = 3*x
3*x - 2*x = 6
x = 6
So, one more solution found:
1/2 = 1/6 + 1/3
We cannot go further as y becomes equal to 2.
Full answers:
1/2 = 1/4 + 1/4
1/2 = 1/6 + 1/3
Let us look at the second sample:
Start with y = 12 * z = 12 * 2 = 14:
1/12 = 1/24 + 1/24 --Obvious :-)
Reduce y to 23:
Using (1) above we get:
12 = (x * 23)/(x + 23)
12 * (x + 23) = 23 * x
12*x + 276 = 23*x
276 = 11*x
x = 276/11 = 25.0909 => NOT a solution as we need 11 to exactly divide 276
Reduce y to 22:
Using (1) above we get:
12 = (x * 22)/(x + 22)
12*x + 12 * 22 = 22 * x
12 * 22 = 10 * x => NOT a solution
Reduce y to 21:
Using (1) above we get:
12 = (x * 21)/(x + 21)
12 * (x + 21) = 21 * x
12*x + 12 * 21 = 21*x
12 * 21 = 9*x
x = 28 => We have a solution :-)
1/12 = 1/28 + 1/21
Reduce y to 20:
Using (1) above we get:
12 = (x * 20)/(x + 20)
12*x + 12*20 = 20*x
12*20 = 8*x
x = 30 => we have a solution :-)
1/12 = 1/30 + 1/20
Reduce y to 19:
Using (1) above we get:
12 = (x * 19)/(x + 19)
12*x + 12*19 = 19*x
12*19 = 7*x
x = 32.57 => NOT a solution
Reduce y to 18:
Using (1) above we get:
12 = (x * 18)/(x + 18)
12*x + 12*18 = 18*x
12*18 = 6*x
x = 36 => we have a solution :-)
1/12 = 1/36 + 1/18
Reduce y to 17:
Using (1) above we get:
12 = (x * 17)/(x + 17)
12*x + 12*17 = 17*x
12*17 = 5*x
x = 40.8 => NOT a solution
Reduce y to 16:
Using (1) above we get:
12 = (x * 16)/(x + 16)
12*x + 12*16 = 16*x
12*16 = 4*x
x = 48 => we have a solution :-)
1/12 = 1/48 + 1/16
Reduce y to 15:
Using (1) above we get:
12 = (x * 15)/(x + 15)
12*x + 12*15 = 15*x
12*15 = 3*x
x = 60 => we have a solution :-)
1/12 = 1/60 + 1/15
Reduce y to 14:
Using (1) above we get:
12 = (x * 14)/(x + 14)
12*x + 12*14 = 14*x
12*14 = 2*x
x = 84 => we have a solution :-)
1/12 = 1/84 + 1/14
Reduce y to 13:
Using (1) above we get:
12 = (x * 13)/(x + 13)
12*x + 12*13 = 13*x
12*13 = 1*x
x = 156 => we have a solution :-)
1/12 = 1/156 + 1/13
END when y = 12
There you go :-)
There could be some optimization that can be performed for quickly
discarding some values of y. Will update.
