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!