We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Editorial says setters solution is sqrt(n)logn but I don't think it is. Complexity of finding coprime numbers less than m for n is not logn. It's rather 2^k where k is number of distinct prime factors.
Although my solution is actually sqrt(n)log(sqrt(n)), it is different than setter solution and much more complex which uses mobius function, properties of multiplicative and summatory functions and some other things. I don't use the idea of summing over co-prime numbers. Rather I sum over f(i) and find a way to sum them efficiently. I think setter's solution complexity is a lot more than s/he thinks it is
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Coprime Conundrum
You are viewing a single comment's thread. Return to all comments →
Editorial says setters solution is sqrt(n)logn but I don't think it is. Complexity of finding coprime numbers less than m for n is not logn. It's rather 2^k where k is number of distinct prime factors.
Although my solution is actually sqrt(n)log(sqrt(n)), it is different than setter solution and much more complex which uses mobius function, properties of multiplicative and summatory functions and some other things. I don't use the idea of summing over co-prime numbers. Rather I sum over f(i) and find a way to sum them efficiently. I think setter's solution complexity is a lot more than s/he thinks it is