Getting the Basics Right with CodeMonk 2.0 and Hackerrank
DAY 0:
Behold the CodeMonk 2.0 series. This came as a BLESSING. It covers almost all the basics in a series of fun competitions and tutorials.
However, I've observed that a lot of the problems accompanied with the tutorial are of inferior quality, or the wording of the question is vague. So, to counter that problem I'll be frequently visiting the hackerrank platform looking for questions of higher quality for the topic I would be practicing at that moment.
Will keep a log of the progress !!
The code monk challenges have a set of basic topics that are intended to be covered before you move on the "meaty" stuff.
The most interesting and most useful of these basic topics is BIT MANIPULATION. It dives into the core of how digits are represented inside the computer ( 0 / 1 ) and give one the superpower to solve problems efficiently in almost constant time, which would have otherwise taken quadratic time. It may almost seem like magic to the people who don't have sufficiently developed bit manipulation skills.
In this question, one is supposed to report the count of numbers that satisfy the following condition : XORing a number A and any number strictly lesser than A that produces a result that is greater than A should be counted .
So ! What does one do ?! Well, bit manipulation comes to the rescue.
THAT"S IT!! JUST 1 Line of code for a solution !! How about that haan!!!
However, the question remains !! How does this work?!? What's it's complexity ?! and what's even happening in this code ?!
Will be back to explain everything ............... till then chow !!
Day 1:Starting with the basics:
The most interesting and most useful of these basic topics is BIT MANIPULATION. It dives into the core of how digits are represented inside the computer ( 0 / 1 ) and give one the superpower to solve problems efficiently in almost constant time, which would have otherwise taken quadratic time. It may almost seem like magic to the people who don't have sufficiently developed bit manipulation skills.
Let's take an example The Great XOR ( Hackerrank )
In this question, one is supposed to report the count of numbers that satisfy the following condition : XORing a number A and any number strictly lesser than A that produces a result that is greater than A should be counted .
Now the range given on A is pretty damn high (as large as 10^10 to be specific ) and there are 10^5 testcases to be solved . The time that is expected for execution is about 2 seconds ( that's about 10^8 operations ).
As we can see that it's impossible to check the XOR of every number less than A, as that will take 10^5 *(10^10) , which will take about 11 days !!! and ain't nobody got time for dat !
As we can see that it's impossible to check the XOR of every number less than A, as that will take 10^5 *(10^10) , which will take about 11 days !!! and ain't nobody got time for dat !
So ! What does one do ?! Well, bit manipulation comes to the rescue.
I would not be surprised if you see the solution and are SHOCKED and AMAZED at the same time.
*** I'd suggest you give the question a try before you look at the code, so that you're truly able to appretiate the elegance of the solution***
**spoiler code follows**
THAT"S IT!! JUST 1 Line of code for a solution !! How about that haan!!!
However, the question remains !! How does this work?!? What's it's complexity ?! and what's even happening in this code ?!
Will be back to explain everything ............... till then chow !!
Comments
Post a Comment