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.
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 →
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 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.