The Kth factor of N - an O(sqrt n) algorithm

Introduction

Recently I wrote the post Learn Big O Notation once and for all. In that post I go over all of the types of Big O time notation that is available at the Big-O cheatsheet. And I did not think there would be any more time notations possible outside of those seven.

As if the universe itself was humbling me and mocking my ignorance, I encountered a LeetCode problem with a solution of O(√n) time. Which could be translated to O(N^1/2), if you're crazy.

The problem

You are given two positive integers n and k. A factor of an integer n is defined as an integer i where n % i == 0.

Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors.

The obvious solution

Well, if you're like me your first thought was to go through every number from 1 to n, check if it is a factor, and if it is in the desired k index, return it.

The code looks like this:

def getkthFactorOfN(n, k):
    result = 0
    for i in range(1, n + 1):
        if n % i == 0:
            result = result + 1
            if result == k:
                return i
    return -1

This is all fine and dandy, but it is "only" O(n). After all, there is only one loop and it goes up to n + 1.
Every other operation is discarded when considering the time notation.

But, my friend, there's a catch.

Understanding factors

If you think about it, factors are "mirrored" after a certain point.

Take, for example, the number 81. Its factors are [1, 3, 9, 27], where:

• 1 * 81 = 81
• 3 * 27 = 81
• 9 * 9 = 81
• 27 * 3 = 81
• 81 * 1 = 81

If you don't count the number 9, The operations are simply repeated and flipped. If you divide n by one of its factors, you get another factor.
Expect the square root of n, where it is itself squared (duh).

Armed with this knowledge, we now know that we don't need to iterate through the loop up to n times (with range(1, n + 1)), but simply up to math.sqrt(n). After that, we've got every factor we need!

The not-so-obvious solution

Now that we have everything we need, we need to transform this loop from 1 -> n to 1 -> sqrt n.

I'll just throw the code here and we'll go over the lines one by one.

def getkthFactorOfN(n, k):
    i = 1
    factors_asc = []
    factors_desc = []
    while i * i <= n:
        if n % i == 0:
            factors_asc.append(i)
            if i != n // i:
                factors_desc.append(n // i)
        i += 1
    if k <= len(factors_asc):
        return factors_asc[k-1]
    k -= len(factors_asc)
    if k <= len(factors_desc):
        return factors_desc[-k]
    return -1

Oof, it's way more complex. Let's break it down:

First, we initialize i = 1. This variable will be used as the "number we're currently at" while searching for factors.

Second, we'll create two arrays: factors_asc and factors_desc. The magic here is that we are going to add factors to factors_asc - they're named like this because they'll be automatically in ascending order.
Whenever we add something to factors_asc, we'll divide n by it and add it to factors_desc. Similar logic here; they'll be conveniently added in descending order.

Then, we begin our loop. Here I've changed it to be while i * i <= n, since we stop when we hit the root of n.

We begin by checking if the current number is a factor (n % i == 0). If so, we can append it to our factors_asc array.

Next, we get the "reverse factor" of i. We can do this by checking if i != n // i, or in other words, if it is not the root. This is because the root must not be duplicated in both arrays. If it isn't, we get the reversed factor by running n // i and appending the result in factors_desc.

After that, we add 1 to i and continue our loop.

After the loop is done, we must have every factorial we need.

We begin by checking if k is in the first half including the root (which can be interpreted as the middle) with if k <= len(factors_asc). If so, get the index from this array (remember: arrays begin at zero!).

If not, we must subtract the amount of factors found from k and check again - with k -= len(factors_asc) and if k <= len(factors_desc).

If k is inside factors_desc, get its value with factors_desk[-k] (from last to first).

If all fails, return -1.

The curve

If you're wondering where in the curves graph it lands, it would be between O(n) and O(log n), being better than the former and worse than the latter. Here's a graph:

Available at Mathspace

Conclusion

This was a ride to uncover and research. Thank you so much for reading up to this point.

If you want to be more optimized, you can create factors_asc_len and factors_desc_len variables and add +1 every time you append a value to these arrays, so that the method len() doesn't have to be called, since this method is O(n) so it can impact time notation.

Good luck in your studies and until next time!