Skip to content

Swap only two digits resulting in a minimum number

July 8, 2013

An interesting algorithmic question:

“Given a string of digits 0-9, swap only two digits such that it produces the smallest number possible with the restriction that you can not have leading zeros in the number. For example, 101, can not be swapped into 011.

The simple approach would be O(k^2), where k is the number of digits in the string. The algorithm I posted below runs in worst case O((radix+1)*k) – linear by length of input with a constant of the radix plus the scan to find the rightmost index of each number.

Advertisements

From → Algorithms

Leave a Comment

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

%d bloggers like this: