One of the very tricky questions asked in an interview.
Swap the values of two variables like a=10 and b=15.
Generally to swap two variables values, we need 3rd variable like:
temp=a;
a=b;
b=temp;
Now the requirement is, swap values of two variables without using 3rd variable.
This question is related to
c++
Of course, the C++ answer should be std::swap.
However, there is also no third variable in the following implementation of swap:
template <typename T>
void swap (T &a, T &b) {
std::pair<T &, T &>(a, b) = std::make_pair(b, a);
}
Or, as a one-liner:
std::make_pair(std::ref(a), std::ref(b)) = std::make_pair(b, a);
You may do....in easy way...within one line Logic
#include <stdio.h>
int main()
{
int a, b;
printf("Enter A :");
scanf("%d",&a);
printf("Enter B :");
scanf("%d",&b);
int a = 1,b = 2;
a=a^b^(b=a);
printf("\nValue of A=%d B=%d ",a,b);
return 1;
}
or
#include <stdio.h>
int main()
{
int a, b;
printf("Enter A :");
scanf("%d",&a);
printf("Enter B :");
scanf("%d",&b);
int a = 1,b = 2;
a=a+b-(b=a);
printf("\nValue of A=%d B=%d ",a,b);
return 1;
}
Stupid questions deserve appropriate answers:
void sw2ap(int& a, int& b) {
register int temp = a; // !
a = b;
b = temp;
}
The only good use of the register keyword.
The best answer would be to use XOR and to use it in one line would be cool.
(x ^= y), (y ^= x), (x ^= y);
x,y are variables and the comma between them introduces the sequence points so it does not become compiler dependent. Cheers!
that's the correct XOR swap algorithm
void xorSwap (int* x, int* y) {
if (x != y) { //ensure that memory locations are different
if (*x != *y) { //ensure that values are different
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
}
you have to ensure that memory locations are different and also that the actual values are different because A XOR A = 0
As already noted by manu, XOR algorithm is a popular one which works for all integer values (that includes pointers then, with some luck and casting). For the sake of completeness I would like to mention another less powerful algorithm with addition/subtraction:
A = A + B
B = A - B
A = A - B
Here you have to be careful of overflows/underflows, but otherwise it works just as fine. You might even try this on floats/doubles in the case XOR isn't allowed on those.
No-one has suggested using std::swap, yet.
std::swap(a, b);
I don't use any temporary variables and depending on the type of a and b the implementation may have a specalization that doesn't either. The implementation should be written knowing whether a 'trick' is appropriate or not. There's no point in trying to second guess.
More generally, I'd probably want to do something like this, as it would work for class types enabling ADL to find a better overload if possible.
using std::swap;
swap(a, b);
Of course, the interviewer's reaction to this answer might say a lot about the vacancy.
R is missing a concurrent assignment as proposed by Edsger W. Dijkstra in A Discipline of Programming, 1976, ch.4, p.29. This would allow for an elegant solution:
a, b <- b, a # swap
a, b, c <- c, a, b # rotate right
If you change a little the question to ask about 2 assembly registers instead of variables, you can use also the xchg operation as one option, and the stack operation as another one.
Let's see a simple c example to swap two numbers without using the third variable.
program 1:
#include<stdio.h>
#include<conio.h>
main()
{
int a=10, b=20;
clrscr();
printf("Before swap a=%d b=%d",a,b);
a=a+b;//a=30 (10+20)
b=a-b;//b=10 (30-20)
a=a-b;//a=20 (30-10)
printf("\nAfter swap a=%d b=%d",a,b);
getch();
}
Output:
Before swap a=10 b=20 After swap a=20 b=10
Program 2: Using * and /
Let's see another example to swap two numbers using * and /.
#include<stdio.h>
#include<conio.h>
main()
{
int a=10, b=20;
clrscr();
printf("Before swap a=%d b=%d",a,b);
a=a*b;//a=200 (10*20)
b=a/b;//b=10 (200/20)
a=a/b;//a=20 (200/10)
printf("\nAfter swap a=%d b=%d",a,b);
getch();
}
Output:
Before swap a=10 b=20 After swap a=20 b=10
Program 3: Making use of bitwise XOR operator:
The bitwise XOR operator can be used to swap two variables. The XOR of two numbers x and y returns a number which 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).
#include <stdio.h>
int main()
{
int x = 10, y = 5;
// 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)
printf("After Swapping: x = %d, y = %d", x, y);
return 0;
Output:
After Swapping: x = 5, y = 10
Program 4:
No-one has suggested using std::swap, yet.
std::swap(a, b);
I don't use any temporary variables and depending on the type of a and b the implementation may have a specialization that doesn't either. The implementation should be written knowing whether a 'trick' is appropriate or not.
Problems with above methods:
1) The multiplication and division based approach doesn’ work if one of the numbers is 0 as the product becomes 0 irrespective of the other number.
2) Both Arithmetic solutions may cause arithmetic overflow. If x and y are too large, addition and multiplication may go out of integer range.
3) When we use pointers to a variable and make a function swap, all of the above methods fail when both pointers point to the same variable. Let’s take a look 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
Let us see the following program.
#include <stdio.h>
void swap(int *xp, int *yp)
{
*xp = *xp ^ *yp;
*yp = *xp ^ *yp;
*xp = *xp ^ *yp;
}
int main()
{
int x = 10;
swap(&x, &x);
printf("After swap(&x, &x): x = %d", x);
return 0;
}
Output:
After swap(&x, &x): x = 0
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 the swapping.
#include <stdio.h>
void swap(int *xp, int *yp)
{
if (xp == yp) // Check if the two addresses are same
return;
*xp = *xp + *yp;
*yp = *xp - *yp;
*xp = *xp - *yp;
}
int main()
{
int x = 10;
swap(&x, &x);
printf("After swap(&x, &x): x = %d", x);
return 0;
}
Output:
After swap(&x, &x): x = 10
second_value -= first_value;
first_value += second_value;
second_value -= first_value;
second_value *= -1;
#include<iostream.h>
#include<conio.h>
void main()
{
int a,b;
clrscr();
cout<<"\n==========Vikas==========";
cout<<"\n\nEnter the two no=:";
cin>>a>>b;
cout<<"\na"<<a<<"\nb"<<b;
a=a+b;
b=a-b;
a=a-b;
cout<<"\n\na="<<a<<"\nb="<<b;
getch();
}
public void swapnumber(int a,int b){
a = a+b-(b=a);
System.out.println("a = "+a +" b= "+b);
}
Consider a=10, b=15:
Using Addition and Subtraction
a = a + b //a=25
b = a - b //b=10
a = a - b //a=15
Using Division and multiplication
a = a * b //a=150
b = a / b //b=10
a = a / b //a=15
Maybe off topic, but if you know what you are swapping a single variable between two different values, you may be able to do array logic. Each time this line of code is run, it will swap the value between 1 and 2.
n = [2, 1][n - 1]
a = a + b
b = a - b // b = a
a = a - b
a = a + b - (b=a);
It's very simple, but it may raise a warning.
Since the original solution is:
temp = x; y = x; x = temp;
You can make it a two liner by using:
temp = x; y = y + temp -(x=y);
Then make it a one liner by using:
x = x + y -(y=x);
Swapping two numbers using third variable be like this,
int temp;
int a=10;
int b=20;
temp = a;
a = b;
b = temp;
printf ("Value of a", %a);
printf ("Value of b", %b);
Swapping two numbers without using third variable
int a = 10;
int b = 20;
a = a+b;
b = a-b;
a = a-b;
printf ("value of a=", %a);
printf ("value of b=", %b);
the general form is:
A = A operation B
B = A inverse-operation B
A = A inverse-operation B
however you have to potentially watch out for overflows and also not all operations have an inverse that is well defined for all values that the operation is defined. e.g. * and / work until A or B is 0
xor is particularly pleasing as it is defined for all ints and is its own inverse
#include <iostream>
using namespace std;
int main(void)
{
int a,b;
cout<<"Enter a integer" <<endl;
cin>>a;
cout<<"\n Enter b integer"<<endl;
cin>>b;
a = a^b;
b = a^b;
a = a^b;
cout<<" a= "<<a <<" b="<<b<<endl;
return 0;
}
Update: In this we are taking input of two integers from user. Then we are using the bitwise XOR operation to swap them.
Say we have two integers a=4 and b=9 and then:
a=a^b --> 13=4^9
b=a^b --> 4=13^9
a=a^b --> 9=13^9
You could do:
std::tie(x, y) = std::make_pair(y, x);
Or use make_tuple when swapping more than two variables:
std::tie(x, y, z) = std::make_tuple(y, z, x);
But I'm not sure if internally std::tie uses a temporary variable or not!
single line solution for swapping two values in c language.
a=(b=(a=a+b,a-b),a-b);
#include <stdio.h>
int main()
{
int a, b;
printf("Enter A :");
scanf("%d",&a);
printf("Enter B :");
scanf("%d",&b);
a ^= b;
b ^= a;
a ^= b;
printf("\nValue of A=%d B=%d ",a,b);
return 1;
}
In javascript:
function swapInPlace(obj) {
obj.x ^= obj.y
obj.y ^= obj.x
obj.x ^= obj.y
}
function swap(obj) {
let temp = obj.x
obj.x = obj.y
obj.y = temp
}
Be aware to execution time of both options.
By run this code i measured it.
console.time('swapInPlace')
swapInPlace({x:1, y:2})
console.timeEnd('swapInPlace') // swapInPlace: 0.056884765625ms
console.time('swap')
swap({x:3, y:6})
console.timeEnd('swap') // swap: 0.01416015625ms
As you can see (and as many said), swap in place (xor) take alot time than the other option using temp variable.
Here is one more solution but a single risk.
code:
#include <iostream>
#include <conio.h>
void main()
{
int a =10 , b =45;
*(&a+1 ) = a;
a =b;
b =*(&a +1);
}
any value at location a+1 will be overridden.
Source: Stackoverflow.com