Thread: A better algorithm

I was given this assignment:

There is one integral solution to the equation (a^5)+(b^5)+(c^5)+(d^5)+(e^5)=(f^5) that satisfies 1 <= a <= b <= c <= d <= e <= f <= 75. Find the solution.

My algorithm works btw, the answers are a = 19, b = 43, c = 46, d = 47, e = 67, f = 72.

I have done this assignment in C and Java (it has to be turned in as Java code and I don't know any good Java BBSs. I did it in C so I could find help here), but its a sucky algorithm. Its of O(n^5), maybe O(n^6). I think that its the best it can be. It is just one of those problems that requires brute force. I've looked at this for a few days and can't see a better way.

The code:

Code:

#include<stdio.h>
#include<math.h>

#define NOT_FOUND -1

int binarySearch(double *n, int n_size, double z)
{
	int low = 0;
	int mid = 0;
	int high = n_size;

	while(low <= high)
	{
		mid = (low + high) / 2;

		if(n[mid] < z)
		{
			low = mid + 1;
		}
		else if(n[mid] > z)
		{
			high = mid - 1;
		}
		else
		{
			return mid;
		}
	}

	return NOT_FOUND;
}

int main(int argc, char *argv[])
{
	int i = 0,
		a = 0,
		b = 0,
		c = 0,
		d = 0,
		e = 0;

	int f = 0;
	double x[75];

	for(i = 0; i < 75; i++)
	{
		x[i] = pow((i + 1), 5);
	}

	for(a = 0; a < 75; a++)
		for(b = a; b < 75; b++)
			for(c = b; c < 75; c++)
				for(d = c; d < 75; d++)
					for(e = d; e < 75; e++)
					{
						if((f = binarySearch(x, 74, (x[a] + x[b] + x[c] + x[d] + x[e]))) != NOT_FOUND)
						{
							printf("a = %d, b = %d, c = %d, d = %d, e = %d\nf = %d", (a + 1), (b + 1), (c + 1), (d + 1), (e + 1), (f + 1));
							return 0;
						}
					}
	return 0;
}

Any hints & help would be appreciated.

spoon_

Check the web for answers. Big Oh notation of o^5- not sure about that!

In this case, simpler seems to be much faster:

Code:

#include<stdio.h>

int main()
{
        int i,
        a = 0,
        b = 0,
        c = 0,
        d = 0,
        e = 0,
        f = 0;

    double asum, bsum, csum, dsum, esum;
    double pow[75];
    for (i = 1; i < 75; i++)
        pow[i] = (double)i*i*i*i*i;

    for(f=74;f>1;f--)
    {

    for(a = 0, asum = 0; a < f; a++)
        {
            asum = pow[a];

            for(b = a, bsum = 0; b < f && bsum < pow[f]; b++)
            {
                bsum = asum + pow[b];
                for(c = b, csum = 0; c < f && csum < pow[f]; c++)
                {
                    csum = bsum + pow[c];
                    for(d = c, dsum = 0; d < f && dsum < pow[f]; d++)
                    {
                        dsum = csum + pow[d];
                        for(e = d, esum = 0; e < f && esum <= pow[f]; e++)
                        {
                            esum = dsum + pow[e];
                            if(esum == pow[f])
                            {
                                printf("a = %d, b = %d, c = %d, d = "
                                    "%d, e = %d, f = %d\n",a,b,c,d,e,f);
                                printf("pow[f] = %.0f\n",pow[f]);

                                return 0;
                            }
                        }
                    }
                }
            }
        }
    }
    printf("Not found.\n");

    return 0;
}

Ahh, yes. Thats a different way of doing it and is definately faster than my first post.

However, I found another way of doing it that is slightly faster than yours (about 1.25-1.50 seconds).

I just introduced a low variable to the binary search routine and passed the variable e into it. I based this on the fact that e is going to be equal to or less than f, so why not just start searching at index e.

Code:

#include<stdio.h>
#include<math.h>

#define NOT_FOUND -1

int binarySearch(double *list, int list_size, double find_this, int low)
{
	int mid;
	int high = list_size;

	while(low <= high)
	{
		mid = (low + high) / 2;

		if(list[mid] < find_this)
		{
			low = mid + 1;
		}
		else if(list[mid] > find_this)
		{
			high = mid - 1;
		}
		else
		{
			return mid;
		}
	}

	return NOT_FOUND;
}

int main(int argc, char *argv[])
{
	int i = 0,
		a = 0,
		b = 0,
		c = 0,
		d = 0,
		e = 0;

	int f = 0;
	double x[75];

	for(i = 0; i < 75; i++)
	{
		x[i] = pow((i + 1), 5);
	}

	for(a = 0; a < 75; a++)
	{
		for(b = a; b < 75; b++)
		{
			for(c = b; c < 75; c++)
			{
				for(d = c; d < 75; d++)
				{
					for(e = d; e < 75; e++)
					{
						if((f = binarySearch(x, 74, x[a] + x[b] + x[c] + x[d] + x[e], e)) != NOT_FOUND)
						{
							printf("a = %d, b = %d, c = %d, d = %d, e = %d\nf = %d", (a + 1), (b + 1), (c + 1), (d + 1), (e + 1), (f + 1));
							return 0;
						}
					}
				}
			}
		}
	}

	printf("Not Found\n");
	return 0;
}