Search code examples
c++algorithmradix

How I can speed up my algorithm?

I'm solving some problems and I can't solve these one. I have to write a code where user enter a decimal number, and I need to count how many times that number starts with digit 1 in other numerous systems. Here is algorithm:

for (int i = 3; i <= n; i++) {
    int z = n;
    while (z != 0) {
        x = z % i;
        z = z / i;
    }
    if (x == 1) {
        brOsnova++;
    }
}
Solution

  • You can accelerate it already by not checking the i's that verify

    i <= n < 2*i since all of them will satisfy. Therefore, check only for(int i = 3; i <= n/2; ++i) and then add (n+1)/2 to the final brOsnova.

    I am sure it can be further accelerated and there must be some O(log(n)) algorithm, but maybe it would be far fetched... or a good candidate question for the algorithm tag.