Sort Integers by The Number of 1 Bits With Python and Rust

Created on Jan 7, 2021

When I was coding with Rust to solve this problem, I thought I was dealing with memory so harshly and also thought that time will not be very optimized.

Until I saw this:

Screenshot from leetcode by Ezz

it took 4 ms to run and 2.3 MB of memory. Comparing the same algorithm I did with Python means Rust in this problem is 22 times as fast as Python and takes space in memory less than 6ish times as Python takes.

Now, don’t get me wrong! This is not the best performance Rust can do in this problem, my code is just faster than the third of Rust submissions at leetcode and only ~22% less in memory usage than the Rust submissions at the platform.

But if you’ve found another language competing this number with the same algorithm, comment below I’d like to see which language can beat that!

This blog post is just comparing almost the same algorithm with two programming languages. Let’s see this simple algorithm and at the end, you can see the codes embedded.

Understanding the Problem

Sory Integers by The Number of 1 Bits is an easy problem at leetcode, I hope you have read the problem carefully and have tried solving it. This problem requires you to sort the integers you’re given based on how many ones each integer has in its binary representation. So how can we know the binary representation of each integer in order to count them and sort their associated elements?

Decimal integer to binary conversion

One way to solve such a problem is to convert each given integer to its associated binary and then count the ones, store them, do zipping to their associated integers coming from the original array, and sort the original integers based on the count of ones that each integer has.

Knowing the fact that there is a base number in the numeric system you’re using allows you to figure out the way it’s written in that way.

Let’s unpack this by showing some examples

Example 1: 2

2 is represented as 10 in binary. By simple integer division and remainder, you can get to this result

result remainder

2/2     1       0
1/2     0       1

The base number in the binary system is 2 so:

Example 2: 3

3 is represented as 11 in binary. Let’s see how we can get that binary

result remainder

3/2     1       1
1/2     0       1

That’s how I thought about this problem and below is my implementations in Python and Rust:



Click here to get fresh content to your inbox

Published on my new medium publication, make sure to follow it: Brainwave

Follow me on Linkedin