355 - The Bases Are Loaded (math numbers conversion) Recently I found this task, which is to convert numbers between arbitrary bases.

My code is working fine, but time limit exceeded.

#include &lt;cstring&gt;
#include &lt;cstdio&gt;


int broj[50], n;
char uzorak[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};

long long ToDec(char a[], long long base)
{
    long long dec = 0, b = 1;
    int l = strlen(a);
    for(int i = l-1; i &gt;= 0; i--)
    {
        if(a[i] &gt;= '0' &amp;&amp; a[i] &lt;= '9')
            dec += (a[i]-'0') * b;
        else
            dec += (a[i] - 'A' + 10) * b;
        b *= base;
    }

    return dec;
}

void ToB2(long long a, int b2)
{
    n = 0;
    while(a &gt; 0)
    {
        broj[n] = a%b2;
        a = (a-broj[n])/b2;
        n++;
    }
    for(int i = n-1; i&gt;=0; i--)
        printf("%c", uzorak[broj[i]]);
}

int main()
{
    char a[50];
    int b1, b2, l;
    while(scanf("%i %i %s", &amp;b1, &amp;b2, &amp;a))
    {
        int base = 1;
        l = strlen(a);
        for(int i = 0; i &lt; l; ++i)
        {
            if(a[i] &gt;= '0' &amp;&amp; a[i] &lt;= '9')
                    base = (base &gt; a[i]-'0') ? base : a[i]-'0';
            else if(a[i] &gt;= 'A' &amp;&amp; a[i] &lt;= 'Z')
                    base = (base &gt; a[i]-'A'+10) ? base : a[i]-'A'+10;
            else
            {
                base = -1;
                goto Break;
            }
        }
        base++;
        Break:
        if((base &lt;= b1)&amp;&amp;(base != -1))
        {
            printf("%s base %i = ", a, b1);
            ToB2(ToDec(a, b1), b2);
            printf(" base %i\n", b2);
        }
        else
            printf("%s is an illegal base %i number\n", a, b1);
    }
    return 0;
}


I would appreciate any suggestions on optimizing my code, thanks!

Is there any faster methods to convert numbers from one base to another or you have to go over base 10?
No, you don't need to convert to base 10. Base 10 is in fact quite slow to operate with, as it is in no way a "native" base for computers, which store integers in binary format.

Let's do the math. Assume you need to convert four digit number from base a to base b. Let x_i denote the digit of the number in base a and y_i the digit in base b:

In base a the number is:

x1*a^3 + x2*a^2 + x3*a^1 + x4*a^0 = ((x1*a + x2)*a + x3)*a + x4


In base b it becomes:

y1*b^3 + y2*b^2 + y3*b^1 + y4*b^0 = ((y1*b + y2)*b + y3)*b + y4


The right side of these equations suggests an algorithm idea: to convert a number to binary format from a string s in base a, start with zero, and in each step multiply the number so-far with a and add the next digit. This requires only one multiplication per loop, not two, like in your approach (although that's not likely the reason why your code is too slow.)

int len = strlen(s);
int i;
unsigned long long number = 0;

for (i = 0; i &lt; len; ++i) {
        unsigned digit;
        if (s[i] &gt;= '0' &amp;&amp; s[i] &lt;= '9') {
                digit = s[i] - '0';
        } else {
                digit = s[i] - 'A' + 10;
        }
        number = number * a + digit;
}


You had the rest of it already: adding for completeness. For conversion to base b, in each step divide by b.

const char digits[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};

char result[50];
/* Note the end condition here: stop when the number becomes zero */
for(i = 0; number != 0; ++i) {
        unsigned digit = number % b;
        number /= b;
        result[i] = digits[digit];
}


Now result contains the digits backwards. To print them in order:

for (; i &gt;= 0; --i) {
        putchar(result[i]);
}


Other minor performance notes


Don't call strlen() twice - there's no need to do it more than once anyway, but if there was, you could cache the result and pass as a parameter.
The code in main that determines whether the input string is acceptable is too complex: no need to do the conversion here, just check if each digit is in the acceptable range.


Unrelated notes about readability:


instead of this:


base = (base &gt; a[i]-'0') ? base : a[i]-'0';

suggest using this:

base = max(base, a[i] - '0');



Avoid variable names like l - easy to confuse with 1.
Use const before read-only variabes (such as the array of digits).