Hackerrank Day 25: Running Time and Complexity

screen-shot-2017-01-02-at-3-11-42-pm

My Solution in Ruby:  

screen-shot-2017-01-02-at-3-10-44-pm

To check if n has any divisors, you only need to check up to the square root of n.  For example, if n = 24, then its divisors are:

1,  2,  3,  4

24, 12, 8, 6

This means if  you’re checking 1, 2, 3, 4, you have also already checked their counterparts, which are 24, 12, 8, 6.  Thus, you can set the upper limit of the range to be the square root of 24 (4.899) to shorten the running time.

 

 

Advertisements
Hackerrank Day 25: Running Time and Complexity

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s