We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

Performance geek here. Nice job. You might want to try improving the runtime by only iterating up to the square root of n instead of n like this to improve your runtime from O(n) to O(n^(1/2)).

Iterating up to sqrt(n) makes our runtime improve from O(n) to O(n^(1/2)). When we are checking a number for divisors, we want to find 2 numbers that multiply into a 3rd number, like this:

a*b=c

In my code, the variables are named differently, so we want

i*n/i=n

Every time we find 1 divisor i, we also add the other divisor n/i to our sum. Since we are adding both sets of divisors, we can get all of them iterating just up to the sqrt(n). If we kept iterating, we would get duplicates.

As an example, if i = 2, n/i = 5, n = 10, we would get 2 * 5 = 10, so we grab both divisors: 2 and 5. If we kept iterating past the square root, we would eventually reach i = 5, n/i = 2, and n = 10, and we would again grab divisors: 5 and 2. We don't want that, so we stop iterating when we reach the square root.

## Day 19: Interfaces

You are viewing a single comment's thread. Return to all comments →

Performance geek here. Nice job. You might want to try improving the runtime by only iterating up to the square root of n instead of n like this to improve your runtime from O(n) to O(n^(1/2)).

Hope this helps.

HackerRank solutions.

any explainations for iterating up to sqrt(n)? and could you please explain sum += i + n/i; part as well?

Thank you.

Iterating up to sqrt(n) makes our runtime improve from O(n) to O(n^(1/2)). When we are checking a number for divisors, we want to find 2 numbers that multiply into a 3rd number, like this:

In my code, the variables are named differently, so we want

Every time we find 1 divisor

i, we also add the other divisorn/ito our sum. Since we are adding both sets of divisors, we can get all of them iterating just up to the sqrt(n). If we kept iterating, we would get duplicates.As an example, if i = 2, n/i = 5, n = 10, we would get 2 * 5 = 10, so we grab both divisors: 2 and 5. If we kept iterating past the square root, we would eventually reach i = 5, n/i = 2, and n = 10, and we would again grab divisors: 5 and 2. We don't want that, so we stop iterating when we reach the square root.

HackerRank solutions.

My realization of what you suggested:

Nice. This line looks a little weird to me:

Any integer % 1 is always 0. So it seems that line is just checking if the square root of

nis an integer or not.HackerRank solutions.

yes, that's what I do to avoid checking

inside the loop.