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 weakness of number
xas the number of positive integers smaller thanxthat have more divisors thanx.It follows that the weaker the number, the greater overall weakness it has. For the given integer
n, you need to answer two questions:
- what is the weakness of the weakest numbers in the range
[1, n]?- how many numbers in the range
[1, n]have this weakness?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 
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.
// 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.
// 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 
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.
// 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.
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]
}
