A recent post on SO has presented this challenge:

Q: Given a positive integer, you are allowed to perform 1 swap to return the smallest possible result. Leading zeros are not allowed.

This question has received quite a lot of attention of SO, as people try to come up with an algorithm with linear runtime. So I thought I would have a crack.Â Coming up with an algorithm that runs in O(n) is simple enough. My python version is below:

This meets all the targets – it runs in linear time, looping through the array once before performing a swap. However it is nagging at me though, there must be a more elegant solution than this. It is close to a sorting algorithm, so perhaps I can use a divide-and-conquer approach, recursion, list-comprehension even?

The first step will be to make a general sorting algorithm I think. Nothing fancy, perhaps it will inspire me to a more imaginative solution for this question. Watch for follow up blogs…

### Like this:

Like Loading...

*Related*

Pingback: Interesting Challenge… Divide and Conquer | :: NickBurns