47
Swapping without a temporary variable : Take Care
Swap
C
C++

This must be the easiest program, after "Hello World", we have ever written.

Even we don't need a compiler to test the result, right? We can submit it blindly if we get such question in our Competitive Programming world, won't we?

Nevertheless, this might be the most frequently asked, most famous question in interviews, oh I forgot, with a additional condition of Don't use any temporary variable! Did your interviewer not ask this?

Today I have few methods for doing the same.

This is going to be a quite short and quick post, but yet I will give you an important/useful note at the end. This is not which I have planned, but it struck my mind and I thought it's worth sharing.

So, Lets start with our different solutions:-

For all the solutions, Consider a & b are our variables. a = 5 and b = 10.

 1. Using the temporary variable

    void swap(int &a, int &b)
    {
        int temp = a;
        a = b;
        b = temp;
    }

2. Without using temporary variable, with addition-subtraction

    void swap(int &a, int &b)
    {
        a = a + b;
        b = a - b;
        a = a - b;
    }

 3. Without using temporary variable, with multiplication-division

    void swap(int &a, int &b)
    {
        a = a * b;
        b = a / b;
        a = a / b;
    }

 4. Without using temporary variable, with XOR operation

    void swap(int &a, int &b)
    {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }

 5. One liner with addition-subtraction

    void swap(int &a, int &b)
    {
        a = a + b - (b = a);
    }

 6. One liner with multiplication-division

    void swap(int &a, int &b)
    {
        a = a * b / (b = a);
    }

 7. One liner with XOR

    void swap(int &a, int &b)
    {
        a ^= b ^= a ^= b;
    }

8. Using a temporary variable, with a macro:

    #define swap(type,a,b) type temp;temp=a;a=b;b=temp;

Cool enough?

Did you not like this?

Though These one liners or without-temporary-variable thing looks cool, simple and tricky, fancy; these have their own problems associated with them.

Lets have look at problems associated with each method.

Methods 2, 3, 5, 6:

Will these methods give you answer if values of a and b are huge?
say MAX_INT is the maximum value of integer that can be accommodated in a and b.
The moment we add a & b, or multiply them, They are going to overflow, they don't fit in our 32 bit size.
We will get WA (wrong answer).

Methods 3, 6:

Will these method work if any of a or b is 0?
We are going to get Divide by zero error.

Methods 4, 7:

These methods appear to be clean, because they don't fail for any test-case, but again since (as in method 7) value of variable is modified twice within the same sequence point, it is undefined behavior declared by ANSI C.

(Those, who are curious about sequence points, I will cover that topic in some other note).

Method 8:

We call that macro from our code as :

swap(int, a, b)

Right?

That macro get substituted in our code as:

int temp;
temp=temp;
temp=b;
b=temp;

To be honest, don't we use some variable as temp?

Again, the name conflict.

To summaries this, I just want to tell you, avoid doing this in any of the above fancy ways (unless asked in interviews :p ). Stick to the basics i.e. Method 1. It is easy to write, easy to maintain too.

Oh, I have one more way :p

A gift for Python programmers:

a, b = b, a

I hope you liked this post.

If you really like this, Let me know! :)

Also have look at my other notes: HERE.

Author

Уведомления

?