Saturday, October 3, 2015

Difference between two numbers in a system with limited operation

One of my friends, Ravi, asked me a question today and he said that it was asked to him by one of his interviewers some time back. Here is the problem statement:

You are designing a new computing system in which following four operations are possible as of now:

(1) Assignment of a variable to another : x = y.
(2) Assignment of zero to a variable : x = 0.
(3) Increment a variable : x++.
(4) Looping in a way which takes a number (variable) as argument and loops for that number (variable) even if you change that variable's value inside the loop. You can't break out of the loop.

How to calculate difference of two numbers "x - y" in the above system?

After spending some time in thinking about the solution, here is what I came up with:

There is one more information given to us. The system is new and designed by us. Hence, we know the architecture of the system and hence the highest positive value possible in that system after which a variable becomes zero if incremented by 1. 
Now, we can assign the highest possible value for that architecture, say 65535 for 16-bit as we are allowed to assign a value to a variable. Then we can increment it twice to get the output as 1. We see that if we add 2 to the highest value we get 1, in a similar fashion, we can add 'n' to the variable having highest value to get 'n-1'. So, we see that in the first iteration, we start with 'n' and get 'n-1'. We can then start with 'n-1' and we will get 'n-2' and so on. We will get 'n-y' after 'y' iteration. Here we can take "x = n". 

Hence we will get "x - y" with the set of operation defined in the problem statement above and one more additional information about the highest number possible in the system. 

No comments:

Post a Comment