**Source**: Quantnet Forums

**Problem**:

A question which is asked on interview in some software development companies.

I guessed 3 natural numbers - x,y,z. You can ask me about two sums of these numbers with any coefficients - a,b,c. For example, you give me a, b and c and I tell you the result of the expression a*x+b*y+c*z. Give me the algorithm to find x,y and z.

**Observation/Hint**:

Irrespective of whether you get the solution, its interesting that you are solving a system of three variables using two equations. You are able to do that because the coefficient in the second equation depends on the answer of the first equation. :)

Update (November 6, 2011):

**Solution**: Posted by Harsh Pareek (Graduate Student at UT Austin, CSE IITB 2011 Alumnus), Rudradev Basak (IITD CSE Senior Undergraduate) and AnonymousD in comments!

Crucial fact: they are natural numbers. If you knew the maximum number of digits any of them can have, say d, you could set a=1, b=10^-(d+1), c=10^-(2d+2), and you would be able to read the numbers off the decimal expansion for the sum.

ReplyDeleteSo, you use the first calculation to find the maximum number of digits, noting that it is okay to overestimate. Set a=1,b=1,c=1.

Let the sum x+y+z=D. and d = ceil(log_10 D). Then 0<x,y,z<10^d.

Then, set a=1,b=10^-d, c = 10^-2d.

Let the sum be S.

Then x = floor(S), y = floor((S-x)*10^d), z = floor( (S-x)*10^(2d) - y * 10^d)

Finally, note that you can actually solve for n natural numbers x_1,x_2,...x_n with just 2 questions.

If we know T is greater than the values of x,y,z, Then it is sufficient to ask a question with a=1, b=T, c=T^2.

ReplyDeleteTo determine a feasible T there are lots of ways, simplest is to ask a question with a=b=c=1, and take the answer as T.

First get x+y+z=n, and then get

ReplyDeletex + n*y + n^2*y and write it down in base n to get x y z as its digits.

All solutions correct and same! Thanks!

ReplyDelete