Project Euler - Problem 14

It has been a while since I last posted on this forum. But I came across a problem once again:

I have been trying to solve Problem 14 of Project Euler
( http://projecteuler.net/problem=14 )

My 'solution' builds successfully, but when I actually run it, I get this error:
Unhandled exception at 0x77ae15de in ProjectEuler.exe: 0xC0000005: Access violation reading location 0xbc4d1a74.

I have no idea how to interpret this error message, so I also have no idea where to start fixing it...

Here is the full code of my solution:
 ``12345678910111213141516171819202122232425`` `````` using namespace std; int i_LargestChainSize = 0; int i_LargestChainNumber = 0; const int n = 1000000; int *Array = new int[n]; memset(Array,0,n); for (int i = 1; i < 1000001; i++) { long b = i; int i_Counter = 1; while (!(b == 1)) { ((b%2) == 0)? b = b/2 : b = (3*b + 1); i_Counter += 1; if ((b-1 < 1000000) && !(Array[b-1] == 0)) { i_Counter += Array[b-1]; b = 1; } } Array[i-1] = i_Counter; if (i_Counter > i_LargestChainSize) { i_LargestChainSize = i_Counter; i_LargestChainNumber = i; } } cout << i_LargestChainNumber << endl;``````

My general strategy is basically counting every step I make, and as soon as I hit a number for which I have already counted the number of steps, I just add those to what I already had.

I hope everything is understandable, because I didn't write it thinking anyone else except for me would ever need to understand it... :P
Maybe that's a good thing to think about in the future.
At some point, on line 12, (3*b+1) will exceed the maximum value a variable of type long can hold, which will cause it to assume a negative value. This means the following if body will be entered, Array will be indexed with that negative number and you will attempt to access memory that you should not.

doesn't seem like you need an array at all for this.
I tried it without an array first, and let the program running for 5 minutes and it still didn't give me the answer. So the array is just to make it a little bit faster (or at least I think I make it faster by doing that...)

@cire: Thanks, I changed the data type to an unsigned long long, and I don't get any errors anymore. However, according to my program, the solution is 937599, whereas it should be 837799.. Does anyone have any idea where this mistake comes from?

Edit: I changed
 ``12345`` ``````i_Counter += 1; if ((b-1 < 1000000) && !(Array[b-1] == 0)) { i_Counter += Array[b-1]; b = 1; }``````

to
 ``1234567`` `````` if ((b-1 < 1000000) && !(Array[b-1] == 0)) { i_Counter += Array[b-1]; b = 1; } else { i_Counter += 1; }``````

Otherwise it would count twice for some numbers

I went through the whole program by hand now (up to i = 4), writing down everything the program should do. And I don't see what could be the problem anymore... The answer I get now is 966655, which is still wrong
Last edited on
Trace through the logic.

When i is 2, what is the length stored in array[1] ?

Hint: It's not 2, although the sequence is { 2, 1 }

Btw, turn optimization's on if you're worried about how long it's taking. Brute forcing it takes under 2 seconds here.
Last edited on
I know it didn't store 2 in my first code, but I don't see why it wouldn't store 2 in my latest version....
when i = 1, it skips the whole while loop and stores 1 in Array[0]
when i = 2:
b = 2 => b is even so b = 1, Array[1-1] is not 0 (since 1 was stored there when i = 1)
therefor, i_Counter now equals itself + what is stored in array[0], which puts i_Counter to 2.
then the while loop is ended since b now equals 1, so i_Counter is stored in Array[1]
So I don't see why it wouldn't store 2 here... Where is the flaw in my logic? :/
You can tell from the times that I was posting at the same time you were editing your post.

There is one other thing I see.

` memset(Array,0,n);`

That sets a number of bytes to 0, so it should be:

` memset(Array,0,n*sizeof(Array[0]));`
I didn't notice you posted it at the same time, sorry about that..

Thank you very much cire, I get the correct answer now :D
Topic archived. No new replies allowed.