I found my new grind. Goodbye Hearthstone. Goodbye World of Warcraft.

Hello, CodeFights.

Arcade Mode was a lot of fun for me today. In The Labyrinth of Nested Loops, I found this little gem :

We define the

weaknessof number`x`

as the number of positive integers smaller than`x`

that have more divisors than`x`

.It follows that the

weakerthe number, the greater overallweaknessit has. For the given integer`n`

, you need to answer two questions:

- what is the
weaknessof theweakestnumbers in the range`[1, n]`

?- how many numbers in the range
`[1, n]`

have thisweakness?Return the answer as an array of two elements, where the first element is the answer to the first question, and the second element is the answer to the second question.

What fun!

This feels like I could brute-force it with a nested loop is and suffer the performance. If I manage to solve it using only sequential loops on the other hand, it would be no matter how many loops I used. I think I scored somewhere in between, maybe depending on what you believe about the inner loops in the following sections.

The problem can be decomposed by first finding the number of divisors, then counting weakness counts (not a typo – counts of counts!), and finally finding the weakest among those.

Finding divisors can be done in many ways. I use variable-stride loops to increment every spot where a given number is a divisor.

1 2 3 4 5 6 |
// Find the number of divisors divisors = new Array(n+1) divisors.fill(0) for (var i=1; i<=n; i++) for (var j=i; j<=n; j+=i) divisors[j]++ |

Next, I want a count of all numbers that have a given number of divisors. This segment of code will end with a variable called `divisorsCounts`

, where `divisorsCounts[3] = 4`

if there are exactly 4 numbers in range that have 3 divisors.

1 2 3 4 5 6 7 |
// Count the counts divisorsCounts = new Array(n) // probably overkill divisorsCounts.fill(0) // Compute the weakness weakness = new Array(n+1) weakness.fill(0) greatestWeakness = 0 |

The array `divisorsCounts`

does not need to be that large, but it’s only memory, right? Apparently something called the Divisor Function has an upper limit of . I’m no number theorist, but I buy it. A factor of two is not even worth typing Math.floor() for, so I’ll leave the code alone as it now looks clean.

1 2 3 4 5 |
for (var me=1; me<=n; me++) { divisorsCounts[divisors[me]]++ for (var j=divisorsCounts.length-1; j>divisors[me]; j--) weakness[me] += divisorsCounts[j] } |

It is key here that I fill the divisorsCounts at the same time as I calculate weakness** . **At any given point in time I have only counted the divisors up to the number I am examining

*For a given number*

**.****m**, weakness is the number of divisor counts

**greater than**

**divisors[m]**found in numbers

**smaller than m**.

I can optimize these loops by shrinking `divisorsCount`

. JavaScript creates sparse arrays by default, and their length is determined by the highest-indexed element. The inner nested loop will be shortened.

1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Count the counts divisorsCounts = [] // Compute the weakness weakness = new Array(n+1) weakness.fill(0) greatestWeakness = 0 for (var me=1; me<=n; me++) { divisorsCounts[divisors[me]] = (divisorsCounts[divisors[me]] | 0) + 1 for (var j=divisorsCounts.length-1; j>divisors[me]; j--) weakness[me] = (divisorsCounts[j] | 0) + weakness[me] } |

The pipes handle undefined elements (note that `x + undefined`

will never produce a number). With `n=500`

, `divisorsCount`

is only 25, so this may improve performance quite a bit.

Finally, I must track the greatestWeakness and how many times it is found.

Here it is in all of its beauty.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
function weakNumbers(n) { // Find the number of divisors divisors = new Array(n+1) divisors.fill(0) for (var i=1; i<=n; i++) for (var j=i; j<=n; j+=i) divisors[j]++ // Count the counts divisorsCounts = [] // Compute the weakness weakness = new Array(n+1) weakness.fill(0) greatestWeakness = 0 greatestWeaknessCount = 0 for (var me=1; me<=n; me++) { divisorsCounts[divisors[me]] = (divisorsCounts[divisors[me]] | 0) + 1 for (var j=divisorsCounts.length-1; j>divisors[me]; j--) weakness[me] = (divisorsCounts[j] | 0) + weakness[me] if (greatestWeakness < weakness[me]) { greatestWeakness = weakness[me] greatestWeaknessCount = 1 } else if (greatestWeakness == weakness[me]) { greatestWeaknessCount++ } } return [greatestWeakness, greatestWeaknessCount] } |