1

I was asked to create a function that is given a positive integer num, and returns a generator, that when iterated over, it will return all of num's divisors in ascending order.

Implementation requirements:

  • Runtime of O(sqrt(n))
  • Memory complexity of O(1)

I was able to meet the runtime requirement but couldn't figure out to solve the problem in O(1) memory (ie. without using a list, tuple, string etc.)

Here's my code so far.

def factors(num):
    higher_divisors = [0] * int(num ** .5)
    index = 0
    for i in range(1, int(num ** .5) + 1):
        if num % i == 0:
            yield i
            if i != num // i: # don't include the square root twice
                higher_divisors[index] = num // i
                index += 1

    for i in range(index - 1, -1, -1): # yield the higher divisors in reverse order
        yield higher_divisors[i]

def main():
    num = 100
    for i in factors(num):
        print(i)

if __name__ == "__main__":
    main()
metatoaster
  • 17,419
  • 5
  • 55
  • 66
Shounak Ghosh
  • 11
  • 4

1 Answers1

2

The trick is to run the loop twice, once forward, once backwards. This will achieve both the time and space complexity requirements.

def factors(num):
    mid = int(num ** .5)
    for i in range(1, mid + 1):
        if num % i == 0:
            yield i
    for i in range(mid, 0, -1):
        if num % i == 0 and (num // i) != mid:
            yield num // i

How the space complexity is satisfied is apparent (i.e. all memory usage is well defined as constant regardless of input).

How the time complexity is satisfied requires a bit of understanding on what Big-O actually means: it ultimately means the shape of the curve which time (or space) requirements grows with regards to the input, i.e. the specific growth rate. This thread has answers that dives into what that means, so best to reference that, and also the wikipedia article on the properties, which states that "if an algorithm runs in the order of n2, replacing n by cn means the algorithm runs in the order of c2n2, and the big-O notation ignores the constant c2." Hence, the algorithm above may look like O(2*sqrt(n)), but given that constants are ignored, it really is O(sqrt(n)).

metatoaster
  • 17,419
  • 5
  • 55
  • 66
  • Yeah, that's a lot cleaner. I got stuck in the mindset that I got both factors in a pair when looping through only once. – Shounak Ghosh Oct 18 '22 at 05:47