F5 Networks Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
-- Filter all factors of n
factorsOfN n = length $ filter ((==0). mod n) [1..n]
-- filter all factors of n from 1..sqrt of n - 1 for squares
factorsOfN' n = (cSqrt - trSq) - 1 + 2*length (filter ((==0) . mod n) [2.. trSq])
where
trSq = truncate $ sqrt $ fI n
cSqrt = ceiling $ sqrt $ fI n
Based on Anonymous's O(sqrt(n)) algorithm. Not entirely sure about the ceil(sqrt(n) + 0.0001) part though.
from math import *
def num_factors(n):
factors = 2
for i in range(2, int(ceil(sqrt(n) + 0.0001))):
if n % i == 0:
factors += 1 if i*i == n else 2
return factors
print num_factors(12)
This solution has the best case scenario complexity of O(log(sqrt(n)). The worst case scenario takes O(sqrt(n)) time. The idea is to find prime factors and their numbers. Then we just need to calculate the numbers each prime factor occurs in the input number.
private int FactorsNumber(int n)
{
var m = n;
var res = 1;
for (int d = 2; d <= Math.Sqrt(m); d++)
{
var k = 1;
while (m % d == 0)
{
m /= d;
k++;
}
if (k > 1) res *= k;
}
if (m > 1) res *= 2;
return res - 1;
}
Is the total number of factors of N to be returned, or return the actual factors as well?
- shah10 December 13, 2014