• C++ Programming for Financial Engineering
    Highly recommended by thousands of MFE students. Covers essential C++ topics with applications to financial engineering. Learn more Join!
    Python for Finance with Intro to Data Science
    Gain practical understanding of Python to read, understand, and write professional Python code for your first day on the job. Learn more Join!
    An Intuition-Based Options Primer for FE
    Ideal for entry level positions interviews and graduate studies, specializing in options trading arbitrage and options valuation models. Learn more Join!

Guess 3 natural numbers

Joined
8/18/10
Messages
153
Points
38
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 a1, b1 and c1 and I tell you the result of the exrepssion a1x+b1y+c1z. Give me the algorithm to find x,y and z.
 
well you can always figure out 2 of the numbers. seems like to get the 3rd you would need to use the fact that they are natural numbers, but I am not sure how.
 
I see this question and I instantly think of modular arithmetic. I'll edit this post when I figure out the answer.
Edit: Actually, now I'm thinking bases!

You could ask x+10^100y+10^200z and obtain x, y, and z in one sum as long as you assume x,y, and z are each less than 100 digits. To verify x,y,z
simply ask
z+10^100y+10^200x. If you obtain the same x,y,z you're done. Now somehow help if you don't get the same x,y,z (that is, at least one of them is more than 100 digits)
 
It's really a combinatorics question at heart.

For the first set of coefficients just pick (1,1,1). Whatever the result is, the number of possible triples (x,y,z) is finite -- they're constrained to the first octant because they're natural numbers, and only a finite number of lattice points on the plane x+y+z=N are in the first octant. Denote the set of possibilities for (x,y,z) by (S). Then all we need to do is find numbers (a,b,c) so that (a(x_1-x_2)+b(y_1-y_2)+c(z_1-z_2)) is never equal to zero for distinct points ((x_1,y_1,z_1),(x_2,y_2,z_2)\in S). in other words, we need a vector (a,b,c) that's not orthogonal to any of the points ((x_1-x_2,y_1-y_2,z_1-z_2)).

And this is pretty easy to find. Here's an algo, though definitely not the most efficient one. Denote the set of points ((x_1-x_2,y_1-y_2,z_1-z_2)) by (T) and let (k) be the number of elements in (T). Then simply search the space ([1,p]\times [1,p]\times [1,p]) where (p=\lceil \sqrt[3]{k}\rceil). Among those vectors there must exist one that's not orthogonal to any of the points in (T) because no two of them can be orthogonal to the same element in (T) (the angle between any two of them is strictly (<90^\circ)) and there are more than (k) of them.

Edit: Oops, that's wrong. This fixes it... Let (T) be as in the crossed out paragraph and let (a=1). Then let (m) be the largest absolute value among all (ax), where (x) is an (x)-coordinate in (T). Let (b=m+1). Then for any ((x,y,z)\in T), (ax+by\neq 0) whenever ((x,y)\neq 0). Now let (p) be the largest absolute value among all (ax+by), where ((x,y,z)\in T). Let (c=p+1), and consider an arbitrary ((x,y,z)\in T).

1. If ((x,y)=0), then clearly (z\neq 0), so (ax+by+cz\neq 0).

2. If ((x,y)\neq 0), then (ax+by\neq 0) by construction, so even if (z=0), we still have (ax+by+cz\neq 0), and if (z\neq 0), then by construction (cz) cannot equal (ax+by) in absolute value, and thus (ax+by+cz\neq 0)
 
Might be simpler...find x + y + z first, that gives the upper bound for the order of x,y,z, say 10^t. See what happens when we ask for x + y/(10^(t+1)) + z/(10^(2t+2))?

Edit: Hadn't read euroazn's solution, similar multiplication after getting the order by x+y+z will work too :P
 
Might be simpler...find x + y + z first, that gives the upper bound for the order of x,y,z, say 10^t. See what happens when we ask for x + y/(10^(t+1)) + z/(10^(2t+2))?

Edit: Hadn't read euroazn's solution, similar multiplication after getting the order by x+y+z will work too :p
Ah, of course! The second one we use different powers of 10 based on the bounds. Thanks for filling in that gap ;)
 
It's really a combinatorics question at heart.

For the first set of coefficients just pick (1,1,1). Whatever the result is, the number of possible triples (x,y,z) is finite -- they're constrained to the first octant because they're natural numbers, and only a finite number of lattice points on the plane x+y+z=N are in the first octant. Denote the set of possibilities for (x,y,z) by (S). Then all we need to do is find numbers (a,b,c) so that (a(x_1-x_2)+b(y_1-y_2)+c(z_1-z_2)) is never equal to zero for distinct points ((x_1,y_1,z_1),(x_2,y_2,z_2)\in S). in other words, we need a vector (a,b,c) that's not orthogonal to any of the points ((x_1-x_2,y_1-y_2,z_1-z_2)).

And this is pretty easy to find. Here's an algo, though definitely not the most efficient one. Denote the set of points ((x_1-x_2,y_1-y_2,z_1-z_2)) by (T) and let (k) be the number of elements in (T). Then simply search the space ([1,p]\times [1,p]\times [1,p]) where (p=\lceil \sqrt[3]{k}\rceil). Among those vectors there must exist one that's not orthogonal to any of the points in (T) because no two of them can be orthogonal to the same element in (T) (the angle between any two of them is strictly (<90^\circ)) and there are more than (k) of them.

Edit: Oops, that's wrong. This fixes it... Let (T) be as in the crossed out paragraph and let (a=1). Then let (m) be the largest absolute value among all (ax), where (x) is an (x)-coordinate in (T). Let (b=m+1). Then for any ((x,y,z)\in T), (ax+by\neq 0) whenever ((x,y)\neq 0). Now let (p) be the largest absolute value among all (ax+by), where ((x,y,z)\in T). Let (c=p+1), and consider an arbitrary ((x,y,z)\in T).

1. If ((x,y)=0), then clearly (z\neq 0), so (ax+by+cz\neq 0).

2. If ((x,y)\neq 0), then (ax+by\neq 0) by construction, so even if (z=0), we still have (ax+by+cz\neq 0), and if (z\neq 0), then by construction (cz) cannot equal (ax+by) in absolute value, and thus (ax+by+cz\neq 0)

This is a great mathematical solution but would never be expected for an on-the-spot software interview answer ;)
But thinking of these as lattice points is pretty clever!
 
This is a great mathematical solution but would never be expected for an on-the-spot software interview answer ;)
But thinking of these as lattice points is pretty clever!

ha, but your solution is easier and probably the one they had in mind.
 
Back
Top