In this article, we will learn about various approaches for swapping two numbers. Lets say we have two variables- FN(first number) and SN(second number). Assume, they hold the values 5 and 6 respectively.
FN = 5 SN = 6
After swapping, you should have,
FN=6 SN = 5
If you just try to store SN in FN,
FN = SN
Both FN and SN becomes 6. The value 5, which was stored in FN will be totally lost. That is why, we make use of a third variable to store one of the numbers temporarily so that we dont loose the value.
Using Temp Variable
While using temp variable, first store any one of the numbers in temp – lets go with FN. As the FN is now safe in the temp variable, we can now replace it with the SN. Finally, SN can be replaced with temp, which has the initial value of the FN.
Temp = FN FN = SN SN = Temp
Often, you will come across a question like – swap two numbers without using any temporary variable. Such questions are framed to encourage you to think logically. Lets think and write our own logic to swap numbers without temp variable.
How to swap without a temp variable
If you are not allowed to use a third variable, somehow you should come up with a combination of the two numbers and store it in one of the variables, so that at any point in time, if you have the combination and any one of the numbers, you can easily get back the other number. Its always better to take examples and then start working with your logic.
Merging the two numbers
So lets think of combining 5 and 6. First thing that comes to my mind is – ‘make it as 56’. Well, it looks easy visually but definitely a bad approach. In order to store 56 in one of the variables, say FN, we should multiply FN by 10 and add the SN. Then, to make SN as 5, which is the tenth decimal place, divide the combination(FN) by 10 ( Make a type cast if needed). Then to make FN as 6, which is the unit place of the combination, find the modulo of the combination. So, the code looks as follows
FN = FN * 10 + SN; SN = FN/10; // Type cast if needed as per the language you use FN = FN % 10;
The code we did works only for single digit numbers. You can try making the above code to work for any number of digits. Perhaps by checking the number of digits in the combination and in the left out number, calculating the number of digits of the number to be found, then divide it by a proper multiple of 10 etc,. etc,. Dont even bother to make such a big code. Its totally unnecessary to write those logics when you can do it a few easy steps. More than that, this approach is so dumb that it makes use of double the space of the input digits to store the combination. Think of swapping two 16 digit numbers, you need the variable capacity of 32 digits which is so unreasonable to ask for. So lets give up this approach. I explained it just as I thought it would definitely pop up in the mind of a naive programmer. But you should be able to figure this all out in a few seconds and start thinking about other methods.
We should probably try using an arithmetic operation like addition. You might ask – why addition. Well, only if we try different things, we can come up with new methods for doing tasks.
Again, lets go with the example before generalizing things. If we add 5 and 6, the sum is 11. You should now store 11 in one of the variables. If you have 11 and 5, 11-5 = 6(yeh, you got the other number). Now, you have 11 and 6, 11- 6 = 5 (just override 11 with 5, and the numbers are swapped).
FN = FN + SN SN = FN - SN FN = FN - SN
Since you have stored the sum in the FN (first line in the code), next you should concentrate on placing the right number in SN. Because you dont want to override the sum immediately after calculating it. Also if you notice, the RHS of last two statements are same. We are subtracting SN from FN(which is the sum) in both steps, but the difference is that the value of SN in last statement is not the same as in the second. It has been modified in the second statement and that is how we are able to make the swapping.
When swapping can be achieved with addition and subtraction, we can try doing the same with multiplication and division. Try applying the same example – 5 and 6. The product is 30. If you have 30 and 5, 30/5 = 6. Similarly 30/6 = 5. With same exact concept, we can swap the two numbers.
FN = FN * SN SN = FN / SN FN = FN / SN
Multiplication approach fails if one of the numbers is 0. If you multiply any number by 0, the result is always 0. If you divide 0 by any number, again the result is 0. There is no way to get back the numbers. So it is better to stick with addition approach.
Both with addition and multiplication approaches, we might encounter arithmetic overflow error. For example, the variables that you are using can hold only 8 digits. If you try and add two bigger 8 digit numbers, you might get a 9 digit number. Since we are using the same variable to store the sum, the 9 digit value will not be stored properly in the variable. Everything will be messed up resulting in arithmetic overflow. We just have to be careful in knowing our input variable ranges and allocating proper variable size for that. Since multiplication might result in bigger number, chances of occurrence of this error is much higher. Another reason to dump multiplication method.
This approach amazes me every time. Lets look at the table for xor first.
From the table, you can see that xor of two same inputs is 0 (first and last row) and xor of two different inputs is 1 (middle two rows). If you try to perform xor again on the output with one of the variable,
(x^y) ^ y = x ^ (y^y) //associative
= x ^ (0) // from the table – 0^0=0, 1^1=0, so y^y=0
= x // from first and third row of the table, it is clear that xor of anynumber with 0 gives the same number
similarly, (x^y)^x = y. We can use this concept to swap the two numbers. Once we have xor output, store it in FN. Perform xor again, with the SN. You will get FN which has to be stored in SN for swapping. Similarly, if you do one more xor – with FN(which has the xor) with SN (which has initial FN value) you will get initial value of SN which can be stored in FN.
FN = FN ^ SN SN = FN ^ SN FN = FN ^ SN
While all the statements in the right had side are same, we are still able to swap the numbers. This is an excellent technique. If you are confused, lets try to do xor and check the working of above code for our examples FN=5 and SN=6.
FN -> 101
FN^SN -> 010 (just do a bit by bit xor by referring the table. Lets call this as output).
If you perform xor for this output with FN,
010 ^ 101 -> 110 (xor of the output with 5 gives 6)
010 ^ 110 -> 101 (xor of the output with 6 gives 5)
You don’t even need any extra space for xor output. As it is a bit wise operator, it will never exceed the space of its original inputs.
When xor fails?
Generally we use the swapping code within functions so that you don’t have to repeat the logic throughout your project. You can just call that function whenever you need to swap. After writing an xor based logic to swap the two values, if you try to pass two pointers to that function which point to the same location,
Now FN and SN are pointers to same location, so FN^SN gives 0 (Though they are pointers, its ultimately going to be a number that is getting stored as address). Lets assume that the variables in the below code are now pointers.
FN = FN ^ SN // FN becomes 0. As they are pointers to same location, SN has also been made 0.
SN = FN ^ SN // FN, SN both remains 0.
FN = FN ^ SN // still the same. both are 0.
The above problem occurs not just with xor. Even for addition or multiplication approach, same thing happens. Lets assume the value passed to FN is 1000. Since both FN and SN are pointers to same location, both has the value of 1000.
FN = FN + SN // FN becomes 2000. Since they are pointers to same location, SN also becomes 2000.
SN = FN – SN // FN, SN becomes 0
FN = FN – SN // still 0
As mentioned before, these kind of questions to swap without temp variable are all just interesting and fun to discuss. It will not work perfectly like using a simple third variable approach. If you are pretty sure your code will not go through the above mentioned failure scenarios, then you can use the alternate approaches discussed.