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 x as the number of positive integers smaller than x that have more divisors than x.

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 O(n^2) performance. If I manage to solve it using only sequential loops on the other hand, it would be O(n) no matter how many loops I used. I think I scored somewhere in between, maybe O(n \log(n)) 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.

    // 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 \sigma_0(i) has an upper limit of n/2. 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.

    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 weaknessAt any given point in time I have only counted the divisors up to the number I am examiningFor 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]
}

CodeFights is awesome! Come find me! Come fight me!

Leave a Reply