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