I bet this question has been asked more than a trillion times in the history of technical interviews and it sounds…..”How to swap variable values with out using a temporary variable?”..as simple as that…ooch…but how?
The most obvious way of doing a swap is by declaring a temp variable
temp = I;
I = J;
J = temp;
But when you say no additional variables to be used, you can always use this age old trick
i = i + j;
j = i - j;
i = i - j;
This has more flavors to follow like, using * / combination instead of + -
i = i * j;
j = i / j;
i = i / j;
And the good news is that, the best of all is yet to come…. the XOR trick
i = i ^ j ;
j = i ^ j;
i = i ^ j;
This one works just fine and is the perfect one suited for any primitive variable types.
So next time some one gives you an intelligent look after this question…don’t forget to prick his ego.
You should take a look at how that XOR trick works; its sort of more interesting than what it seems out from the shell..
Check this…
http://betterexplained.com/articles/swap-two-variables-using-xor/
Good work Steve
So, I declare my variables “struct foo a, b;”, and then swap them by… oh, look, I can’t add or multiply or xor them. Every time I’ve seen this problem posed recently, it’s described as “swap two variables”, never saying that they’re integer or even arithmetic types, yet the solutions always assume that they are…
Obviously, the solution using multiplication doesn’t work if i*j overflows, or if either input is zero. And according to the C spec (and I think the C++ spec follows suit), overflow in addition of signed values results in undefined behavior, so that version only works in the most portable sense for unsigned integral types. (For floating point, either of these approaches is also likely to introduce roundoff errors.)
As for the xor trick, the 1999 C spec allows a couple of (rarely used) signed integer representations that have “negative zero” values that might be created by the xor. It also allows a negative zero to be turned into a positive zero. So if a negative zero is generated by an xor between two values differing only in the sign bit, and then turned into a normal zero, the next xor won’t flip the sign bit of the other value like you’d want it to, and you’ll get an incorrect result. I haven’t checked the C++ spec, or the 1989 C spec it borrows from.
If you don’t mind writing implementation-dependent code, though, the xor trick will work for signed types as well on most platforms. And if you’re writing at the assembly level, or otherwise operating on bytes instead of C types, on most platforms the xor trick will work regardless of the data types stored. But you should be aware that you’re stepping outside the bounds of what the language spec guarantees will be portable.
And, let’s not think too hard about C++ class types where the assignment operator and constructors make some interesting use of ‘this’ internally to the object. Then, a swap of bit patterns by low-level xor operations may break some invariants that the class implementation tries to maintain…
There is another brilliant solution
b=a-b+(a=b);
:P:P:P:P
Abhiram: No, that code snippet results in “undefined behavior”. (Simply put: You’re not guaranteed whether the evaluation of the first “a” gets you the original or the version newly assigned from “b”. It’s a bit more subtle than that, but you get the idea.)
So, like the other solutions, sometimes it’ll work, and sometimes it won’t.
@ken
You are absolutely right. I dont know why, but I was so terribly impressed when I saw that. Forgive my ignorance.
All the methods you listed have limitations. Read the below articles:
http://avsharath.googlepages.com/swapnotemp.html
and:
http://prokutfaq.byethost15.com/SwapTwoNumbersWithoutTemporary
Awesom…this was the basic interview question…..the interviewerwas impressed with tis answer thank you