Given two variables, x, and y, swap two variables without using a third variable.
Method 1 (Using Arithmetic Operators):
Example 1: The idea is to get a sum in one of the two given numbers. The numbers can then be swapped using the sum and subtraction from the sum.
Javascript
<script> // Javascript program to swap two // numbers without using temporary // variable let x = 10, y = 5; console.log("Before Swapping: x = " + x + ", y = " + y); // Code to swap 'x' and 'y' // x now becomes 15 x = x + y; // y becomes 10 y = x - y; // x becomes 5 x = x - y; console.log("After Swapping: x = " + x + ", y = " + y); </script> |
Output:
Before Swapping: x = 10, y = 5 After Swapping: x = 5, y = 10
Time Complexity: O(1).
Auxiliary Space: O(1).
Example 2: Multiplication and division can also be used for swapping.
Javascript
<script> // Javascript program to swap two numbers // without using a temporary variable var x = 10; var y = 5; console.log("Before swapping:" + " x = " + x + ", y = " + y); // Code to swap 'x' and 'y' x = x * y; // x now becomes 50 y = x / y; // y becomes 10 x = x / y; // x becomes 5 console.log("After swapping:" + " x = " + x + ", y = " + y); </script> |
Output:
Before Swapping: x = 10, y = 5 After Swapping: x = 5, y = 10
Time Complexity: O(1).
Auxiliary Space: O(1).
Method 2 (Using Bitwise XOR):
The bitwise XOR operator can be used to swap two variables. The XOR of two numbers x and y returns a number that has all the bits as 1 wherever bits of x and y differ. For example, XOR of 10 (In Binary 1010) and 5 (In Binary 0101) is 1111, and XOR of 7 (0111) and 5 (0101) is (0010).
Example: Below is the example that will illustrate the swap two numbers using Bitwise XOR Method:
Javascript
<script> // Javascript code to swap using XOR let x = 10, y = 5; console.log("Before Swapping: x =" + x + ", y=" + y); // Code to swap 'x' (1010) and 'y' (0101) x = x ^ y; // x now becomes 15 (1111) y = x ^ y; // y becomes 10 (1010) x = x ^ y; // x becomes 5 (0101) console.log("After Swapping: x =" + x + ", y=" + y); </script> |
Output:
Before Swapping: x = 10, y = 5 After Swapping: x = 5, y = 10
Time Complexity: O(1).
Auxiliary Space: O(1).
Problems with the above methods:
1: The multiplication and division-based approach doesn’t work if one of the numbers is 0 as the product becomes 0 irrespective of the other number.
2: Both Arithmetic solutions may cause an arithmetic overflow. If x and y are too large, addition and multiplication may go out of the integer range.
3: When we use pointers to variable and make a function swap, all the above methods fail when both pointers point to the same variable. Let’s take a look at what will happen in this case if both are pointing to the same variable.
// Bitwise XOR based method x = x ^ x; // x becomes 0 x = x ^ x; // x remains 0 x = x ^ x; // x remains 0 // Arithmetic based method x = x + x; // x becomes 2x x = x - x; // x becomes 0 x = x - x; // x remains 0
Example 1: Let us see the following program:
Javascript
<script> function swap(xp, yp) { xp[0] = xp[0] ^ yp[0]; yp[0] = xp[0] ^ yp[0]; xp[0] = xp[0] ^ yp[0]; } // Driver code let x = [10]; console.log("Before swap(&x, &x): x = " + x[0]); // Calling Swap Function swap(x, x); console.log("After swap(&x, &x): x = " + x[0]); </script> |
Output:
Before swap(&x, &x): x = 10 After swap(&x, &x): x = 0
Time Complexity: O(1).
Auxiliary Space: O(1).
Example 2: Swapping a variable with itself may be needed in many standard algorithms. For example, see this implementation of QuickSort where we may swap a variable with itself. The above problem can be avoided by putting a condition before swapping.
Javascript
<script> function swap(xp, yp) { // Check if the two addresses are the same if (xp == yp) return; xp[0] = xp[0] + yp[0]; yp[0] = xp[0] - yp[0]; xp[0] = xp[0] - yp[0]; } // Driver Code x = 10; console.log("Before swap(&x , &x) : x = " + x); // Calling swap function swap(x, x); console.log("After swap(&x , &x) : x = " + x); </script> |
Output:
Before swap(&x , &x) : x = 10 After swap(&x , &x) : x = 10
Time Complexity: O(1).
Auxiliary Space: O(1).
Method 3 (A mixture of bitwise operators and arithmetic operators):
The idea is the same as discussed in Method 1 but uses Bitwise addition and subtraction for swapping.
Example: Below is the implementation of the above approach.
Javascript
<script> function swap(a, b) { // same as a = a + b a = (a & b) + (a | b); // same as b = a - b b = a + (~b) + 1; // same as a = a - b a = a + (~b) + 1; console.log("After swapping: a = " + a + ", b = " + b); } let a = 5, b = 10; console.log("Before swapping: a = " + a + ", b = " + b); // Function Call swap(a, b); </script> |
Output:
Before swapping: a = 5, b = 10 After swapping: a = 10, b = 5
Time Complexity: O(1).
Auxiliary Space: O(1), since no extra space has been taken.
Method 4 (One Line Expression): We can write only one line to swap two numbers.
- x = x ^ y ^ (y = x);
- x = x + y – (y = x);
- x = (x * y) / (y = x);
- x , y = y, x (In Python)
Example: Below is the implementation of the above approach.
Javascript
<script> // Javascript program to swap two // numbers without using temporary // variable let x = 10, y = 5; console.log("Before Swapping: x = " + x + ", y = " + y); // Code to swap 'x' and 'y' x = (x * y)/(x = y); console.log("After Swapping: x = " + x + ", y = " + y); </script> |
Output:
Before Swapping: x = 10, y = 5 After Swapping: x = 10, y = 5
Time Complexity: O(1).
Auxiliary Space: O(1).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
