Give a method to swap two numbers without using additional memory.
Click here to see the solution.
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.
Courtesy: Vibhaj
Hints:
Do you really think this needs a hint? If you can't solve it, you can't.
|
|
Solution:
We may use addition/subtraction or XOR to achieve this.
XOR does not cause overflows and hence is superior.
Complexity:
Time : O(1)
Space : O(1)
void swap_xor(int &num1, int &num2){
num1 ^= num2;
num2 ^= num1;
num1 ^= num2;
}
void swap(int &num1, int &num2){
num1 = num1 + num2;
num2 = num1 - num2;
num1 = num1 - num2;
}
|
|
|
Posts
Pardon me if I sound frivolous,but if additional memory implies JUST an extra variable,then,the following simple algo can be used:
swap(int a, int b)
{a= b-a;
b= b-a;
a= a+b;
}
It can be achieved using XOR operator. To swap a and b we have:
a^=b^=a^=b;
@Manoj: You are absolutely right in your words, don't worry :)
@Ankit: You too are correct
There are two methods "using XOR" and "using Addition/Subtraction"
But XOR does not cause overflow, hence it is better :)