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.

publicintdivisorSum(intn){intsum=0;intsqrt=(int)Math.sqrt(n);// Small optimization: if n is odd, we can't have even numbers as divisorsintstepSize=(n%2==1)?2:1;for(inti=1;i<=sqrt;i+=stepSize){if(n%i==0){// if "i" is a divisorsum+=i+n/i;// add both divisors}}// If sqrt is a divisor, we should only count it onceif(sqrt*sqrt==n){sum-=sqrt;}returnsum;}

You can graph y = x^(1/2) and also graph y = x on the same graph. See which one increases faster as you go from left to right on the graph. After graphing, does that make any sense? Since y = x increases faster, it means the solution is not very scalable.

Not really. sqrt is obtained by integer casting; what you suggested might end up not accounting for some of the divisors.

Say n = 6.
Then sqrt = (int) Math.sqrt(6) = 2
So your loop would run only once with this statement:
sum += 1+6

After that, i < sqrt so we exit the loop.
Since 2*2 != 6, you don't add 2 to the sum.

So your suggested modification would result in sum = 7 for n = 6, which is the wrong sum.

You have probably caught this but for anyone who have not, always pay close attention to the difference between (< vs <= ) when you do integer casting!

## Day 19: Interfaces

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

## Efficient O(n^(1/2)) solution

From my HackerRank solutions.

Runtime: O(n^(1/2))

Space Complexity: O(1)

can you please share us where i can find that n^1/2 is better than n ?

You can graph y = x^(1/2) and also graph y = x on the same graph. See which one increases faster as you go from left to right on the graph. After graphing, does that make any sense? Since y = x increases faster, it means the solution is not very scalable.

HackerRank solutions.

can you please tell me why you negation of the sum.

If sqrt is a divisor, we end up counting it twice. We do

`sum -=sqrt`

to basically remove the double-count we did earlier.HackerRank solutions.

it would be slightly more efficient, though, to do

`for(... i < sqrt ...)`

and`if (sqrt*sqrt==n) sum += sqrt;`

in the end.Not really. sqrt is obtained by integer casting; what you suggested might end up not accounting for some of the divisors.

Say n = 6. Then sqrt = (int) Math.sqrt(6) = 2 So your loop would run only once with this statement: sum += 1+6

After that, i < sqrt so we exit the loop. Since 2*2 != 6, you don't add 2 to the sum.

So your suggested modification would result in sum = 7 for n = 6, which is the wrong sum.

You have probably caught this but for anyone who have not, always pay close attention to the difference between (< vs <= ) when you do integer casting!

I added some optimisations(there is the half of operations if the number n is odd).

What do you think about it?

Nice optimization. I've updated my solution using your suggestion.

HackerRank solutions.

Thanks. I starred your project.

Also I think "n & 1" is faster than "n % 2".

(Of course, if a compiler doesn't do the optimisation).

PS. Fix the link. It's broken.

Thanks for star. Fixed the link. You're right, n & 1 is probably faster.

little optimezd solution -

https://www.hackerrank.com/challenges/30-interfaces/forum/comments/574259