Trying to write a iterative algorithm but can´t get it to work

Viewed 152

I'm trying to write an algorithm for calculating numbers in a number sequence, starting with { 0, 1, 2 }, where additional numbers are calculated using the formula, n = (n - 1) + (n - 3), resulting in the sequence: { 0, 1, 2, 2, 3, 5, 7, 10, 15, 22, 32, 47, 69, 101 }, etc., using an iterative algorithm.

This is what I have tried:

public long calculate(long n) {
    if (n <= 2) {
        return n;
    } else {
        return (n - 1) + (n - 3);
    }
}

However, when I'm testing it, it doesn't seem to be fully correct. Do you have any ideas on what I can improve?

3 Answers

Looks like you have to keep 3 values before n, so in general you have to keep all sequence before n. To do so, it's better to encapsulate it within separate class.

public final class SequenceMaker {

    private final Map<Long, Long> cache = new HashMap<>();
    private long max = 2;

    {
        for (long n = 0; n <= 2; n++)
            cache.put(n, n);
    }

    public long calculate(long n) {
        if (n > max) {
            for (long i = max + 1; i <= n; i++)
                cache.put(i, cache.get(i - 1) + cache.get(i - 3));

            max = n;
        }
        
        return cache.get(n);
    }
}

And client code could look like this:

public static void main(String... args) {
    SequenceMaker sequenceMaker = new SequenceMaker();

    for (int i = 0; i < 14; i++) {
        System.out.print(sequenceMaker.calculate(i));
        System.out.print(" ");
    }
}

Output: 0 1 2 2 3 5 7 10 15 22 32 47 69 101

P.S. If you do not worry about performance, then you can avoid using caching.

public final class SequenceMaker {

    public long calculate(long n) {
        long[] cache = new long[4];

        for (long i = 0; i <= n; i++) {
            cache[0] = i <= 2 ? i : cache[1] + cache[3];
            cache[1] = cache[2];
            cache[2] = cache[3];
            cache[3] = cache[0];
        }

        return cache[3];
    }
}

Or using Deque:

public final class SequenceMaker {

    public long calculate(long n) {
        Deque<Long> queue = new ArrayDeque<>(3);

        for (long i = 0; i <= n; i++)
            queue.addFirst(queue.size() < 3 ? i
                                            : queue.removeLast() + queue.getFirst());

        return queue.element();
    }
}

The first issue is you did not make the recursive call for (n - 1) and (n - 3). The following code have fixed the issue:

public long calculate(long n) {
    if (n <= 2) {
        return n;
    } else {
        return calculate(n - 1) + calculate(n - 3);
    }
}

The problem you have described here, is very similar to Fibonacci Number. Here you will get an article on how to calculate Fibonacci Number by using both recursive and iterative way. Here is the corresponding iterative algorithm of your problem:

public class Calculate{
    
    public static long calculate(long n) {
        if(n < 3) return n;
        
        int [] cache = new int [3];
        int tmp;
        cache[0] = 0;
        cache[1] = 1;
        cache[2] = 2;
        
        for(int i=3; i<=n; i+=1) {
            tmp = cache[2] + cache[0];
            cache[0] = cache[1];
            cache[1] = cache[2];
            cache[2] = tmp;
        }
        return cache[2];
    }

     public static void main(String []args){
        for(int i=0; i<20; i+=1) {
            System.out.print(" " + calculate(i));
        }
        System.out.println("");
     }
}

Sample Output:

 0 1 2 2 3 5 7 10 15 22 32 47 69 101 148 217 318 466 683 1001

Here you can see, I have only cached last three elements in this series. This is because to calculate n-th entry of this series, we only need to need (n-1)-th and (n-3)-th entry of this series. So, the cache array in this solution acts as a sliding window. If memory is not an issue, you can keep an array of size (n+1).

The trick is recognizing that the sums are sums of nth and nth+2nd elements. So you can do it like this without recursion. But you need to keep track of two earlier elements to do it.

int a = -1;
int b = -0;
int c = 1;
for (int i = 0; i < 14; i++) {
    int v = fnc(a, c);
    a = b;
    b = c;
    c = v;
    System.out.println(v + " ");
}

Prints

0 1 2 2 3 5 7 10 15 22 32 47 69 101 

The method which just adds the appropriate elements

public static int fnc(int a, int c) {
    if (c < 2) {
        return a + 1;
    }
    return a + c;
}

In fact, you don't need a method at all, just do it like this using the earlier values for a,b, and c.

for (int i = 0; i < 14; i++) {
    int v = a + c;
    if (c < 2) {
        v = a + 1;
    }
    
    a = b;
    b = c;
    c = v;
    
    System.out.print(v + " ");
}
Related