Home > Blockchain >  Split number into sum of preselected other numbers
Split number into sum of preselected other numbers

Time:04-21

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
  • Related