1. ## 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_

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

3. 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;
}
}
}
}
}
}
}

return 0;
}```

4. 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;
}
}
}
}
}
}