Combat's Trumpet Log: Coding Journey, Euler Problems 16, 20, 25 and 48

So, I worked on Project Euler problems 16, 20, 25 and 48 over the break. The entire idea of each of these problems is that the numbers involved get way too big for the program to store, so you have to get creative with the number storage.

I decided to store the obscenely large numbers in an array of integers. Then, I needed some way to manipulate the array so that we can add to and multiply numbers into it. All of my solutions to these problems revolve around the following functions:

//assigns source to target
void assign(int target[], int length, int source[])
{
        for(int k = 0; k < length; k++)
        {
                target[k] = source[k];
        }
        return;
}

//Had to alter from problem 48.
void add(int number[], unsigned& lengthNum, int add[], unsigned lengthAdd)
{
        int remainder = 0;
        int temp;
        unsigned k = 0;
        //Adds the arrays together until one or the other array ends
        for(k = 0; k < lengthNum && k < lengthAdd; k++)
        {
                temp = (number[k] + add[k]);
                number[k] = (temp + remainder)%10;
                remainder = (temp + remainder)/10;
        }

        //the following deals with adding the rest of the arrays together once they diverge
        //if lengthAdd ended first
        if(k < lengthNum)
        {
                while(remainder > 0 && k < lengthNum)
              {
                        number[k] = (remainder%10+number[k]);
                        remainder /= 10;
                        k++;
                }
        }
        //if lengthNum ended first
        else if(k < lengthAdd)
        {
              while(remainder > 0 && k < lengthAdd)
              {
                        number[lengthNum++] = (remainder%10+add[k]);
                      remainder /= 10;
                        k++;
                }
        }
        //deals with the remainder
        while(remainder > 0)
        {
                number[lengthNum++] = remainder%10;
                remainder /= 10;
        }
        return;
}

//multiplies the multiplier into the array
void mult(int number[], unsigned& length, const unsigned multiplier)
{
        int temp;
        int remainder = 0;
        //does the multiplying
        for(unsigned k = 0; k < length; k++)
        {
                temp = multiplier*static_cast<int>(number[k]);
                number[k] = (temp+remainder)%10;
                remainder = (temp+remainder)/10;
        }
        //deals with the remainder
        while(remainder > 0)
        {
                number[length++] = remainder%10;
                remainder /= 10;
        }
        return;
}

//adds all the digits in the array together
long sumOfDigits(const int number[], const unsigned length)
{
        long retVal = 0;
        //adds each character together
        for(unsigned k = 0; k < length; k++)
        {
                retVal += static_cast<int>(number[k]);
        }
        return retVal;
}

//prints out the array as a number
void out(int number[], const unsigned length)
{
        cout << "Number: ";
        //prints out each character in reverse order
        for(int k = length - 1; k >= 0; k--)
        {
                cout << static_cast<int>(number[k]);
        }
        cout << endl;
}

I have the individual solutions to the problems, if anyone's interested. Just leave a comment if you have any requests.

Wednesday, December 1, 2010

Coding Journey, Euler Problems 16, 20, 25 and 48