1

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!

Improve this question
0

3 Answers 3

Reset to default
2

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;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

actually no need to check for negative numbers. The first negative value, if any exists in the array, is prepended by at least two positive numbers-- which makes sum constraint violated (no such two numbers > 0 that sum in < 0).
You're right. I was being overly cautious. Thank you :)
Did you test this implementation?
actually, after i implemented it, i ran some junit tests and it would not return true for actual fibonacci sequences, everything else worked. however, after changing this line while (fib1 <= arr.get(0)) { to while (fib1 < arr.get(0)) { i got no more errors
Because, as I "hinted"... it doesn't work. Particularly by the time the 1st while is done, fib1 != arr.get(0) is always true, and this result in an automatic return of false. Code is simply wrong.
|
1 
private boolean isFib(final List<Integer> li) {
    //check if each int is the sum of the two prior ints
    for (int i = 2; i < li.size(); i++) {
        if (li.get(i) != li.get(i - 1) + li.get(i - 2)) {
            return false;
        }
    }

    //reverse the fibonacci sequence and check if we end up at the correct starting point (0, 1)
    int i1 = li.get(0);
    int i2 = li.get(1);

    while (i1 > 0) {
        final int tmp = i1;
        i1 = i2 - i1;
        i2 = tmp;
    }

    return i1 == 0 && i2 == 1;
}
Improve this answer

6 Comments

no, because 2, 2, 4, 6 for example is not a part of the fibbonaci sequence.
Then you are accepting this one: [2 2 4 6 10] which is not part of fibonacci.
Fixed it, checks the first digit. Or not. The point was loop starting from index 2..
Is this a valid fibonacci? [0 5 5 10]
That would be taken care of by a guard if.
|
0

I'd suggest a solution which abstracts Fibonacci sequence generator in a separate Iterator<Integer>, then uses it to check if provided list matches any part of the sequence.

Iterator is quite simple and straightforward:

public static class FiboIterator implements Iterator<Integer> {

    @Override
    public boolean hasNext() { return true; }

    int i = -1, j = -1;   // previous two items of Fibo sequence

    @Override
    public Integer next() {
        int k = (i < 0) ? (j < 0 ? 0 : 1) : (i + j);
        i = j;
        j = k;
        return k;
    }
}

Main checking method:

public static boolean isFibo(List<Integer> seq) {
    if (seq.size() < 3)
        return false;
    final Iterator<Integer> f = new FiboIterator();
    int start = seq.get(0), k;
    while ((k = f.next()) < start);         // roll Fibo to match the starting item in input
    if (start != k)                         // starting item doesn't match
        return false;
    if (start == 1 && seq.get(1) != 1)      // special case: [1, 2, ...]
        f.next(); 
    for (int i = 1; i < seq.size(); i++) {  // check if other items match
        if (seq.get(i) != f.next())
            return false;
    }
    return true;
}

And finally a few unit tests:

@Test
public void testFibo() {
    assertTrue(isFibo(Arrays.asList(0, 1, 1, 2)));
    assertTrue(isFibo(Arrays.asList(1, 1, 2, 3, 5)));
    assertTrue(isFibo(Arrays.asList(1, 2, 3, 5, 8)));
    assertTrue(isFibo(Arrays.asList(5, 8, 13, 21, 34)));

    assertFalse(isFibo(Arrays.asList(1, 2, 0)));
    assertFalse(isFibo(Arrays.asList(1, 0, 1)));
    assertFalse(isFibo(Arrays.asList(5, 5, 10, 15)));
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.