HackerRank Day 25
In this series, I will walk you through Hacker Rank’s 30 days of code challenge day by day.
In Day 25, we will get an intro into algorithmic run time or big O notation.
Please fill out this survey to help give me feedback on how to improve the channel.
http://bit.ly/2nVK9oM
Try solving it yourself!
http://bit.ly/2NOivFt
View my solution for Day 25 at
http://bit.ly/2PysgIa
#OTSC #RunTime #HackerRank
Transcript
Today we’re learning about run time. Run time refers to the general efficiency of an algorithm and it is usually described in terms of worst case scenarios. For example, if you were searching for a book on an unsorted bookshelf: the worse case scenario would be that you search the entire book shelf and the last book you look at is the the one you’re looking for. It could happen that the first book or any book you look at before the last book is the one you are looking at, but when computer scientists refer to Big O notation, we talk about the worst case runtime.
Why does it matter? The main reason is that we want to know how much slower a program or algorithm gets when the size of the input increases. We write this as a function of the inputs n or O(n). A program who’s runtime does not vary with the size of the inputs is called a constant time method or O(1) since the runtime is not a function of the inputs. This usually is a simple function like basic arithmetic or reading a single value. A function that grows at the same rate with the size of the inputs is a linear function O(n). An example of this is finding the largest number in an unsorted array. You need to check all values in the unsorted array to make sure that you have found the largest value.
I am just barely scratching the surface here. Let me know if you want me to cover Run time in more depth in another video.
Let’s get back to today’s task. We want to determine whether a number n is Prime or Not Prime. A prime is a natural number greater than 1 that has no positive divisors other than 1 and itself.
The way we will determine whether a number is prime is to iterate through all numbers between 1 and n and see if any of them divide n evenly. If any of the numbers between the two divide n evenly, then n is not a prime. When we have exhausted all numbers between 1 and n and nothing divides n evenly, then we can be sure n is a prime.
So let’s implement our solution. HackerRank did not help us out in this challenge so we will have to interpret the inputs first.
The first line of each test case is an integer T that tells us the number of test cases we will have.
Each of the T subsequent lines contains an integer n to be tested for primality.
We will print “Not Prime” or “Prime” on a new line for each subsequent integer.
The first thing we will do is to read in the input for the number of test cases and store that in a variable.
Then we will write a for loop to run through all the test cases. Let’s just make the stub for now and come back to it later. In our for loop, we will check each input integer to see if they are prime or not. If they are, we will print Prime. Otherwise we will print Not prime.
Now let’s get to the meat of today’s problem. How do we determine if a number is prime? We know that if a number is less than or equal to 1, it is not prime so for those cases, we can return False.
I know HackerRank wants us to find an optimized solution for finding whether a number is prime or not, but let’s try the brute force method first because it is simpler to understand and code. Whether you are interviewing, or making a production system, go with the simpler solution first. Don’t jump in and go for the hyper optimized solution immediately especially when it is more complex to code and for others to understand. A bug in a complex solution is way harder to debug than a bug in a simple solution.
So let’s use the brute force solution fo testing all numbers between 1 and n exclusive to see if there are any other divisors. For i in range 2 to n, if n modulo i is equal to 0, w return False. If we find no divisors, we will return True after the for loop.
So how to make this run in O(sqrt_n)? Well for every divisor of n less than the sqrt of n, we know that there must be a matching divisor greater than the sqrt of n that will multiply with it to make n. Take 10 for example. The square root 10 is 3 something. 2 is a divisor of 10 below the sqrt of 3. and it has a match as 5 above sqrt of 10 that it multiplies with to make 10.
For that, we need to import the math package to use the square root function. We store the square root of n in the sqrt variable after checking is n is less than or equal to 1. If the square root of n is an integer, we know that n is not prime since it has an integer divisor less than n–its square root! Otherwise, we will limit our for loop to integers between 1 and the sqrt of n. Since range is exclusive, we have to remember to add 1 in case casting sqrt of n to an integer rounds down.
