python / refactoring

An interesting challenge – algorithm in linear runtime

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:

linear_1_v2

 

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…

 

 

Advertisements

One thought on “An interesting challenge – algorithm in linear runtime

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s