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

Solving a leetcode problem comparing runtime and memory usage

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:

  • We divide the integer by 2
  • We get 1 as a result and then we take the floor of it which is 1 again
  • And 0 as a remainder, store this remainder!
  • We take the result and divide it by 2 again we get 0.5 whose floor is 0
  • The remainder here is 1, store it!
  • Going from down to above on the remainder column, we get 10

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

  • Divide 3 by 2
  • We get 1 as a result of integer division
  • And 1as a remainder, store this remainder!
  • We take 1 (the result) and integer divide it by 2 again we get 0
  • The remainder here is 1, store it!
  • Going from down to above on the remainder column, we get 11

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

Python

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

Peace!

Resources

Join the conversation

Get FREE coupons and discounts
on my upcoming courses
when you subscribe!

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.