(Java) Trying to use an ArrayList to create multiples of a Fibonacci Sequence and failing

Question

I was trying out a programming challenge I found, you can find it here if you want to know exactly what the requirements are, but what i'm basically trying to do is to get the lowest possible multiple of a Fibonacci Sequence that contains a given number. So input 13 would output [0, 1, 1, 2, 3, 5, 8, 13]. Input 6 would output [0, 2, 2, 4, 6].

My code works fine for any number in the regular Fibonacci Sequence but for any multiple it just outputs, for exmple if the input is 16, [0, 16] and I can't quite figure out why. Any help would be massively appreciated.

import java.util.Scanner;
import java.util.ArrayList;

public class FibonacciMultiples{
    public static void main(String args[]){

        int target;
        ArrayList<Integer> x = new ArrayList<Integer>();
        x.add(0);


        Scanner input;
        input = new Scanner(System.in);

        System.out.println("Please enter target: ");
        target = input.nextInt();

        int i = 0;
        int j = 1;
        int k = 1;

        while(x.get(i) != target){
            x.add((j*k) + x.get(i));
            i++;
            j = x.get(i-1);

            if(x.get(i) > target){
                x.clear();
                x.add(0);
                i=0;
                j=1;
                k++;
            }
        };

        System.out.println(x);


    }
}

it would greatly help if you gave meaningful names to the variables. I am guessing that k is the changing f(1) value? and what's the meaning of x.add((j*k) + x.get(i)); ? setting new value in a fibonacci seq shuld be as simple as x.add(x.get(x.size()-2) + x.get(x.size()-1)); — Sharon Ben Asher
– Sharon Ben Asher, Commented Nov 8, 2015 at 13:37

Eran · Accepted Answer · 2015-11-08 13:42:47Z

1

The problem is here :

j = x.get(i-1);

You take the j for the next iteration from the list, which means it's already multiplied by k.

Then you multiply it again by k here :

x.add((j*k) + x.get(i));

One way to fix it is change

j = x.get(i-1);

to

j = x.get(i-1)/k;

EDIT :

A much more elegant solution with no multiplications or divisions :

    while(x.get(i) != target){
        x.add(j + x.get(i));
        i++;
        j = x.get(i-1);

        if(x.get(i) > target){
            x.clear();
            x.add(0);
            i=0;
            j=k; // this is the key
            k++;
        }
    };

Now the first elements in the sequence are initialized to 0 and k, which means each element will be k times larger than the corresponding element in the original sequence.

Output for 16 :

[0, 2, 2, 4, 6, 10, 16]

edited Nov 8, 2015 at 13:42

answered Nov 8, 2015 at 13:36

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

David Lawlor Over a year ago

Thanks for the reply, that seems to work perfectly. Although i'm a bit confused as to what the problem was to begin with, honestly, when I multiplied j and k together. I wasn't assigning a new value to j so why would I have had to divide by k later?

Eran Over a year ago

@DavidLawlor When you assign to j the last value from the List - j=x.get(i-1); - this value was already multiplied by k when you added it to the list, and you multiply it again when you calculate the next value to add to the List.

Eran Over a year ago

@DavidLawlor Please note my second solution, with doesn't require any multiplications or divisions. It's more efficient and elegant.

David Lawlor Over a year ago

Oh, okay. I think I understand what you mean now. I do like the second solution you posted though - much more elegant. Thanks a ton. Although i'm noticing when I use the program it still has some gaps, like when I enter 29, I still just get [0, 29]. Any idea what's going on there?

David Lawlor Over a year ago

Prime Numbers! That's what's going on, they screw it up. Guess that makes sense.

|

Sharon Ben Asher · Accepted Answer · 2015-11-08 13:51:51Z

1

an even more elegant solution (IMO) is this:

public static void main(String[] args)
{
    int target;
    Scanner input;
    input = new Scanner(System.in);
    System.out.println("Please enter target: ");
    target = input.nextInt();

    List<Integer> fibonacciList = new ArrayList<>();
    int f1 = 1;  // f1 starts at 1 and is increased until found a match
    do {
        fibonacciList = fibonacci(f1++, target);
    } while (fibonacciList.get(fibonacciList.size()-1) != target);

    System.out.println(fibonacciList);
}

// calculate fibonacci with given f(1) value until
// target is reached (or passed)
public static List<Integer> fibonacci(int f1, int target)
{
    List<Integer> fibonacciList = new ArrayList<>();
    // seed the list with given arg
    fibonacciList.add(0);
    fibonacciList.add(f1);

    while (fibonacciList.get(fibonacciList.size()-1) < target) {
        // build the list by adding last two items
        fibonacciList.add(
                fibonacciList.get(fibonacciList.size()-2) +
                fibonacciList.get(fibonacciList.size()-1));
    }
    return fibonacciList;
}

answered Nov 8, 2015 at 13:51

Sharon Ben Asher

14.5k6 gold badges35 silver badges50 bronze badges

1 Comment

David Lawlor Over a year ago

Thanks a lot for your answer, works just great. I'll take some time to get my head around it if I ever need to do something like this in the future!

Collectives™ on Stack Overflow

(Java) Trying to use an ArrayList to create multiples of a Fibonacci Sequence and failing

2 Answers 2

7 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related