Discussion on Day 19: Interfaces Challenge

jiwan_chung 3 years ago+ 1 comment

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

Thank you.

RodneyShag 3 years ago+ 1 comment

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.

HackerRank solutions.

impex_ua 2 years ago+ 1 comment

My realization of what you suggested:

public int divisorSum(int n) {
        
   if (n == 1) return 1;
        
   int sum = 0;
          
   for (int div = 1; div*div <= n; div++){
      sum +=  n % div == 0 ? div + n / div : 0;
   }
                       
   return Math.sqrt(n) % 1 == 0 ? sum - (int) Math.sqrt(n) : sum;
}

RodneyShag 2 years ago+ 1 comment

Nice. This line looks a little weird to me:

Math.sqrt(n) % 1 == 0

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

HackerRank solutions.

impex_ua 2 years ago+ 0 comments

yes, that's what I do to avoid checking

sum += n == divisor ? 0 : divisor;

inside the loop.