DEV Community

Cover image for Swapping two numbers, w/o a temp variable
Morten Olsrud
Morten Olsrud

Posted on

Swapping two numbers, w/o a temp variable

Todays post will be a short one, but one that covers a really simple algorithm that still might stump you in an interview setting if you don't have a background in math, or if you haven't been doing code puzzles on your spare time.

Getting the feel of it

Let's start with the easier version, just to get a feel for the task.

Write an algorithm that swaps two numbers.

Ok, that is easy enough. In pseudocode:

// The numbers
a = 1
b = 2

// Let's swap
c = a   // c == 1
a = b   // a == 2
b = c   // b == 1

// result
a == 2
b == 1

Ok, we just store the value of a in temporary storage c, set a to the value from b, and then set b to the former value of a, now found in c.

Upping the ante

Let's remove the c from the algorithm, not allowing temporary storage...

Write an algorithm that swaps two numbers, without using extra storage.

Wow, that one is a bit trickier. We can't use any more storage, but we need to swap the numbers. Luckily this involves numbers, and we can leverage math to help us.

// The numbers
a = 1
b = 2

// lets swap
a = a + b   // 1 + 2 = 3 => a == 3, b == 2
b = a - b   // 3 - 2 = 1 => a == 3, b == 1
a = a - b   // 3 - 1 = 2 => a == 2, b == 1

Ok, we first set a to be the sum of both numbers. Then we set b to be the result of subtracting it from the sum, making it be the former value of a. Lastly we set a to be the result of subtracting the former value of a, now stored in b, from the sum, still stored in a. This results in a getting bs old value.

Conclusion

Until I learned this trick the hard way myself in a coding quiz, I was baffled by this question, simply because I have been "trained" to think too much about variables, code, loops and other constructs, and too little in the math-department. This made me attempt to find clever ways of solving it using code, rather than the much simpler math.

I hope you can get some value from this little tip, saving you from the feeling of inadequacy that I felt. Getting stuck on quizzes like this, that are truly simple to solve, but that we tend to overcomplicate, really does not help us manage the impostor syndrome that most of us experience at times.

Good luck with your interviews!

Cheers!

-Morten

Discussion (30)

Collapse
philnash profile image
Phil Nash

What if summing a and b leads to a number that is larger than the maximum integer? This would cause an overflow.

I’d hate for an interview trick like this to lead to real world problems. This is the same issue that was present in every incorrect binary search function (see β€œimplementation issues”).

Collapse
peledzohar profile image
Zohar Peled

Totally agree. Interview tricks should never find their way into production code. In fact, I think that's one of the worst problems in software development technical interviews today - the fact that the problems asked and the solutions expected are in no way applicable in real world situations.

Collapse
hakash profile image
Morten Olsrud Author

Couldn't agree more, but because they do, and because we love Code Wars and similar code quiz sites, discussing these tricks are still needed, and for me at least, fun 😊

Thread Thread
peledzohar profile image
Zohar Peled

Yeah, it is fun.

Collapse
kebby profile image
Tammo 'kb' Hinrichs • Edited on

That's why you usually use XOR for the swap trick :)

a^=b;  // a' = (a^b)
b^=a;  // b' = b ^ (a') = b ^(a^b) = a
a^=b;  // a'' = a' ^ b' = (a^b)^a = b
Collapse
philnash profile image
Phil Nash

Yeah, but not in real code! I'd prefer it were readable over assigning one extra variable. You've got to find some specific conditions to make this the better code to use!

Thread Thread
kebby profile image
Tammo 'kb' Hinrichs

I actually used this in real code once, in an assembly inner loop where I was really running out of registers :), but you're right of course.

Related question: Did anyone here ever have to reverse a string? :D

Thread Thread
hakash profile image
Morten Olsrud Author

Not in an interview, but in a quiz somewhere. It was an entry level one so only restriction was to not use the built in functions.

Collapse
marcoslooten profile image
Marco Slooten

Cool way of doing that πŸ™‚

I was immediately thinking about this in JavaScript specifically. You could also use array destructuring to get the same result:

[a, b] = [b, a];
Collapse
thepeoplesbourgeois profile image
Josh

Ruby, too! It's been possible at least since 1.8

a, b = b, a
Collapse
donut87 profile image
Christian Baer

Oh dear...
The task was to do this "without extra space" and not "don't use an extra variable". Both your solutions fail that. Constructing two arrays is definitely extra space used, you just won't see it in your code.
I don't know what Ruby does, but I can imagine, that this will create some variable 'behind the scene' or will also have to arrays constructed.
I am very sorry, but you both failed the test.
This is not very bad though. In real life you only need to know this kind of 'tricks' when you have very limited hardware like small chips in small devices such as smart lamps or smoke detectors. Also in most applications you probably won't need to switch the values of two variables.

Thread Thread
thepeoplesbourgeois profile image
Josh

As always, this is why it's important to understand what the language is doing before calling somebody wrong πŸ™‚

Y'see, no variable in Ruby ever holds the object in question, but instead holds a reference to the object. a, b = b, a tells Ruby to place a reference to whatever is referenced by b at the time of invocation inside of the reference a, and whatever is referenced by a at the time of invocation inside of the reference b. No array construction, no invisible intermediary variable, just happy-go-lucky references, reassigning themselves to the underlying addressed memory locations.

Thx 4 the patronization tho! πŸ’–πŸ’–πŸ˜˜

Thread Thread
donut87 profile image
Christian Baer

As I said, I am not sure what Ruby does and how this parallel assignment really works under the hood.
For the python example (and this was the main focus), my statement holds :-). It's a construction of an array (list), that is assigned to another list and afterwards deconstructed.

Thread Thread
thepeoplesbourgeois profile image
Josh

Good try, but no. "You both fail" is geared quite equally toward two intended audiences. Again, understand what the language is doing before you call someone wrong 😊

Collapse
clavinjune profile image
Clavin June • Edited on

Why don't u use XOR operator?
a = a XOR b
b = a XOR b
a = a XOR b

Collapse
hakash profile image
Morten Olsrud Author

Cool trick!

Collapse
mateiadrielrafael profile image
Matei Adriel

In js u can use ^ as xor

Collapse
joelnet profile image
JavaScript Joel

Swapping two objects, w/o a temp variable

const K = a => b => a

let a = 'A'
let b = 'B'

a = K(b)(b = a)

a //=> 'B'
b //=> 'A'
Collapse
moopet profile image
Ben Sinclair

If someone asked me this in an interview, I'd ask them for an example of where they used it in their production code.

Collapse
mateiadrielrafael profile image
Matei Adriel

To be honest we were teached this in the first week of high school in our c++ class:)

Collapse
hakash profile image
Morten Olsrud Author

Well, I guess it varies from country to country, and school to school, plus, a lot of us does not have a Bachelor or better in anything 😊 We still lovez us some codez tho! πŸ˜‰

Collapse
mateiadrielrafael profile image
Matei Adriel

Yeah, i said it as a fun fact:)

Collapse
glyphcat profile image
GlyphCat

Hmm… what if the variables are of other data types? Just making a guess tho, do people convert those data into bytes then perform the same math?

Collapse
hakash profile image
Morten Olsrud Author

I wouldn't expect people to actually do this, it's more of a puzzle to see if you are able to think outide the box I think.

Collapse
harinsimhadri profile image
Something Unusual

Python
a, b = b, a

Collapse
hakash profile image
Morten Olsrud Author

Cool!

Collapse
thejoezack profile image
Joe Zack

Nice trick!

Collapse
hakash profile image
Morten Olsrud Author

Thanks!

Collapse
Sloan, the sloth mascot
Comment deleted
Collapse
nyc4m profile image
Baptiste Prunot

Seems to work perfectly fine πŸ€”