Robert - 2 months ago 11

Java Question

I'm trying to learn Java a bit on my own

and normally I have more then enough resources with good site's like these,

but now I just want to know where I'm wrong.

So the problem was phrased as :

The following iterative sequence is defined for the set of positive

integers:

n → n/2 (n is even) n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following

sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this

sequence (starting at 13 and finishing at 1) contains 10 terms.

Although it has not been proved yet (Collatz Problem), it is thought

that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one

million.

I keep getting these java.lang.StackOverflowError, could someone help me please.

My code:

`import java.util.HashMap;`

public class Euler

{

HashMap<Integer,Integer> check;

int result;

public Euler()

{

check = new HashMap<Integer,Integer>();

}

public int search(int number)

{

int startingNumber = number;

while (check.get(number)==null && number!=1){

if (number%2==0){

number = number / 2;

result = search(number);

result++;

}

else {

number = (3*number)+1;

result = search(number);

result++;

}

}

if (check.get(startingNumber)!=null){

result=result+check.get(number);

check.put(startingNumber,result);

}

else{

check.put(startingNumber,result);

}

return result;

}

public int test()

{

int temp = 0;

int highest=0;

int get = 0;

for (int i=1000001;i>1;i--){

result = 0;

temp = search(i);

if(temp>highest){

highest=temp;

get = i;

}

System.out.println(i);

}

return get;

}

}

EDIT:

`public class Euler`

{

public Euler()

{

}

public int quickSearch(int numb)

{

int steps = 0;

while (numb != 1) {

if (numb % 2 == 0) {

numb /= 2;

}

else {

numb = 3 * numb + 1;

}

steps++;

}

return steps;

}

public int test()

{

int temp = 0;

int highest=0;

int get = 0;

for (int i=1;i<1000001;i=i+2){

temp = quickSearch(i);

if(temp>highest){

highest=temp;

get = i;

}

System.out.println(i);

}

return get;

}

}

EDIT2:

So in the EDIT version code, i got a freeze from the machine, but when i changed int to long, it worked perfectly, although I understand that with some Map to store values, you can find it faster. Thank you all !!

Answer

The problem is, that you have too many recursive calls. The best resolution for this would be to make the code iterative. Just rework your `while`

loop to first check whether the number was found already if yes return the sum of the steps it took you to get to that number and it will take to get from that number to `1`

. Otherwise just update the number for the next step, run through the loop again. Meanwhile, you just have to keep track of the steps it took you to get to a known number.

Personally, I would remove the `HashMap`

altogether and just have a simple `while`

loop:

```
int steps = 0;
while (number != 1) {
if (number % 2 == 0) number /= 2;
else number = 3 * number + 1
steps++;
}
```

Edit: If you want to add a `HashMap`

to store found values, you could do it like this (I assume you defined a `HashMap<Long, Integer>`

named `foundNumbers`

earlier):

```
public int search(long number) {
int steps = 0;
long initialNumber = number;
while (number != 1) {
if (number % 2 == 0) number /= 2;
else number = 3 * number + 1
steps++;
if (foundNumbers.containsKey(number)) {
steps += foundNumbers.get(number)
foundNumbers.put(initialNumber, steps);
return steps;
}
}
foundNumbers.put(initialNumber, steps);
return steps;
}
```

Source (Stackoverflow)

Comments