Swapping two variable value without using third va

Question

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.

Answer 1

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);

Answer 2

#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

Answer 3

#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;
}

Answer 4

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

Answer 5

a = a + b
b = a - b // b = a
a = a - b

Answer 6

Have you looked at XOR swap algorithm?