Meowzen - 6 months ago 19
Java Question

# Java: check if arraylist is part of fibonacci sequence

My assignment for school is to implement a method that checks if a given

`ArrayList`
is part of the Fibonacci sequence.

The array must not be empty and must be bigger than 3.

I understood that I have to check if one number of the array and the next one are part of the Fibonacci sequence, however I have a lot of trouble with it since you're supposed to accept the array if it's any part of the sequence and not just from the start.

e.g.:
`0 1 1 2 3 5`
will be accepted as well as
`2 3 5 8 13 21`
.

This is my code so far. I know it's very flawed but i really have no clue how to move on.

``````public class ArrayCheck {
/**
* Tests if the given array is a part of the Fibonacci sequence.
*
* @param arr array to be tested
* @return true if the elements are part of the fibonacci sequence
*/
public boolean isFibonacci(ArrayList<Integer> arr) {
//check if array exists
if(arr.size() == 0)
return false;

//check if array is bigger than 3
if (arr.size() < 3)
return false;

//check for the startsequence of 0,1,1
else if(arr.get(0) == 0 && arr.get(1) == 1 && arr.get(2) == 1)
return true;

//check every number in array
for(int i = 0; i < arr.size(); i++) {
//check if i >= 2 is fib
if(i >= 2) {
int fibn = i;
int nextfib = i + 1;

int fibnew = (fibn - 1) + (fibn - 2);
int fibnext = (nextfib - 1) + (nextfib - 2);

if (arr.get(i) != fibnew && arr.get(i + 1) != fibnext)
return false;
}
//check if the order is right
if(arr.get(i) > arr.get(i+1))
return false;
}
return true;
}
``````

Any help is greatly appreciated!

Well, you have a few issues with your code. First of all, if you array is at least 3 items, you check if only the first three are the start of the Fibonacci sequence:

``````//check for the startsequence of 0,1,1
else if(arr.get(0)==0 && arr.get(1)==1 && arr.get(2)==1){
return true;
}
``````

This is bad, as this mean `0 1 1 5` which is not part of the sequence will return true.

What you need to do is split this into two tasks:

• Find the first relevant number in the sequence (i.e. if the array starts with `7`, you know this isn't a part of the sequence; alternatively, if it starts with `8`, you know you need to start checking from `8` onward).
• Once you've found the "start", simply check that the rest of the array follows the Fibonacci rule. you'll need to manually verify the first two items.

``````public boolean isFibonacci(ArrayList<Integer> arr) {

if (arr.size() < 3){
return false;
}

/** find if the first element is part of the sequence: **/

int fib1 = 0;
int fib2 = 1;

while (fib1 <= arr.get(0)) {
int tmp = fib1 + fib2;
fib1 = fib2;
fib2 = tmp;
}

if (fib1 != arr.get(0)) {
// first element is not part of Fibonacci sequence
return false;
}

if (fib2 != arr.get(1)) {
// the first two elements are not part of the Fibonacci sequence
return false;
}

/*** now simply verify that the rest of the elements uphold the rule:
each element is the sum of the two previous ones: **/

for(int i=2; i < arr.size(); i++) {

// make sure there are no negatives in the array:
if (arr.get(i) < 0)
return false;

if (arr.get(i) != (arr.get(i-1) + arr.get(i-2))
return false;

}

//everything checks out okay - return true:
return true;
}
``````