Swapping two variable value without using third variable

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

User · Answer

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

User · Answer

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

User · Answer

Using the xor swap algorithm  void xorSwap  int  x  int  y        if  x    y      ensure that memory locations are different         x     y          y     x          x     y             Why the test     The test is to ensure that x and y have different memory locations  rather than different values   This is because  p xor p    0 and if both x and y share the same memory location  when one is set to 0  both are set to 0  When both  x and  y are 0  all other xor operations on  x and  y will equal 0  as they are the same   which means that the function will set both  x and  y set to 0   If they have the same values but not the same memory location  everything works as expected   x   0011  y   0011   Note  x and y do not share an address  x    y   x    x xor  y     x   0011 xor 0011   So  x is 0000   y    x xor  y     y   0000 xor 0011   So  y is 0011   x    x xor  y     x   0000 xor 0011   So  x is 0011    Should this be used     In general cases  no  The compiler will optimize away the temporary variable and given that swapping is a common procedure it should output the optimum machine code for your platform   Take for example this quick test program written in C    include  lt stdlib h gt   include  lt math h gt    define USE XOR   void xorSwap int  x  int  y       if   x    y             x     y           y     x           x     y           void tempSwap int  x  int  y       int t      t    y       y    x       x   t      int main int argc  char  argv         int x   4      int y   5      int z   pow 2 28        while   z--            ifdef USE XOR             xorSwap  amp x  amp y           else             tempSwap  amp x   amp y           endif           return x   y          Compiled using   gcc -Os main c -o swap   The xor version takes   real    0m2 068s user    0m2 048s sys  0m0 000s   Where as the version with the temporary variable takes   real    0m0 543s user    0m0 540s sys  0m0 000s

User · Answer

a   a   b b   a - b    b   a a   a - b

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

You may do    in easy way   within one line Logic       include  lt stdio h gt   int main         int a  b      printf  Enter A          scanf   d   amp a       printf  Enter B          scanf   d   amp b       int a   1 b   2      a a b  b a       printf   nValue of A  d B  d   a b        return 1      or   include  lt stdio h gt   int main         int a  b      printf  Enter A          scanf   d   amp a       printf  Enter B          scanf   d   amp b       int a   1 b   2      a a b- b a       printf   nValue of A  d B  d   a b        return 1

User · Answer

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

User · Answer

a   a   b -  b a     It s very simple  but it may raise a warning

User · Answer

include  lt iostream gt  using namespace std  int main void        int a b   cout lt  lt  Enter a integer   lt  lt endl   cin gt  gt a   cout lt  lt   n Enter b integer  lt  lt endl   cin gt  gt b     a   a b    b   a b    a   a b     cout lt  lt   a    lt  lt a  lt  lt     b   lt  lt b lt  lt 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 -- gt  13 4 9  b a b -- gt  4 13 9  a a b -- gt  9 13 9

User · Answer

include  lt stdio h gt   int main         int a  b      printf  Enter A          scanf   d   amp a       printf  Enter B          scanf   d   amp b       a    b      b    a      a    b      printf   nValue of A  d B  d   a b       return 1

User · Answer

second value -  first value  first value     second value  second value -  first value  second value    -1

User · Answer

Let s see a simple c example to swap two numbers without using the third variable   program 1    include lt stdio h gt   include lt conio h gt  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 lt stdio h gt   include lt conio h gt  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  lt stdio h gt  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  lt stdio h gt  void swap int  xp  int  yp         xp    xp    yp       yp    xp    yp       xp    xp    yp     int main       int x   10    swap  amp x   amp x     printf  After swap  amp x   amp x   x    d   x     return 0      Output   After swap  amp x   amp 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  lt stdio h gt  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  amp x   amp x     printf  After swap  amp x   amp x   x    d   x     return 0      Output   After swap  amp x   amp x   x   10

User · Answer

Here is one more solution but a single risk   code    include  lt iostream gt   include  lt conio h gt  void main      int a  10   b  45     amp a 1     a  a  b  b     amp a  1       any value at location a 1 will be overridden

User · Answer

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

User · Answer

include lt iostream h gt   include lt conio h gt  void main     int a b  clrscr    cout lt  lt   n          Vikas             cout lt  lt   n nEnter the two no     cin gt  gt a gt  gt b  cout lt  lt   na  lt  lt a lt  lt   nb  lt  lt b  a a b  b a-b  a a-b   cout lt  lt   n na   lt  lt a lt  lt   nb   lt  lt b  getch

User · Answer

Of course  the C   answer should be std  swap   However  there is also no third variable in the following implementation of swap   template  lt typename T gt  void swap  T  amp a  T  amp b        std  pair lt T  amp   T  amp  gt  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

User · Answer

public void swapnumber int a int b       a   a b- b a       System out println  a     a    b    b

User · Answer

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     lt - b  a           swap a  b  c  lt - c  a  b        rotate right

User · Answer

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

User · Answer

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

User · Answer

Stupid questions deserve appropriate answers   void sw2ap int amp  a  int amp  b      register int temp   a         a   b    b   temp      The only good use of the register keyword

User · Answer

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

User · Answer

single line solution for swapping two values in c language   a  b  a a b a-b  a-b

[c++] Swapping two variable value without using third variable

Examples related to c++