I have a number (for example 301, but can be even 10^11).

n = lenght of that number

I have to break it down to sum of max n components. Those components are 0^n, 1^n, 2^n, 3^n...9^n.

How can I do that?

CodePudding user response：

Since you have 1^n included in your options, this becomes a really simple problem solvable through Greedy Approach.

Firstly, let me clarify that the way I understand this, for an input N of length n, you want some solution to this equation:

A.1^n   B.2^n   C.3^n   ...   H.8^n   I.9^n

There are infinitely many possible solutions (just by theory of equations). One possible solution can be found as follows:

a = [x ** n for x in range(0,10)]
consts = [0] * 10
ctr = 9
while N > 0:
    consts[ctr] = N // a[ctr]
    N = N % a[ctr]
    ctr -= 1
return consts

This consts array will have the constant values for the above equation at respective indices.

PS: I've written this in python but you can translate it to C as you want. I saw that tag later. If you have any confusion regarding the code, feel free to ask in the comments.

CodePudding user response：

You could use the following to determine the number of components.

    int remain = 301;   // Target number
    int exp = 3; // Length of number (exponent)
    int total = 0; // Number of components
    bool first = true; // Used to determinie if plus sign is output
    for ( int comp = 9; comp > 0; --comp )
    {
        int count = 0; // Number of times this component is needed
        while ( pow(comp, exp) <= remain )
        {
              total; // Count up total number of components
              count; // Count up number of times this component is used
            remain -= int(pow(comp, exp));
        }
        if ( count ) // If count is not zero, component is used
        {
            if ( first )
            {
                first = false;
            }
            else
            {
                printf("   ");
            }
            if ( count > 1 )
            {
                printf("%d(%d^%d)", count, comp, exp);
            }
            else
            {
                printf("%d^%d", comp, exp);
            }
        }
    }
    if ( total == exp )
    {
        printf("\r\nTarget number has %d components", exp);
    }
    else if ( total < exp )
    {
        printf("\r\nTarget number has less than %d components", exp);
    }
    else
    {
        printf("\r\nTarget number has more than %d components", exp);
    }

Output for 301:

6^3   4^3   2(2^3)   5(1^3)
Target number has more than 3 components

Output for 251:

6^3   3^3   2^3
Target number has 3 components