Project Euler - Problem 14

[simpleasy]

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:

	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.

[cire]

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.

[Lowest0ne]

doesn't seem like you need an array at all for this.

[simpleasy]

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

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

to

			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

[cire]

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.

[simpleasy]

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? :/

[cire]

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]));

[simpleasy]

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