Find the nth element in a tribonacci series

Question

I found this as a Microsoft interview question (see Round 4). I am trying to solve it using C#. My attempt:

private static int NTerm_Tribonacci(int term)
        {
            int a = 0;
            int b = 1;
            int c = 1;
            int result = 0;
            if (term == 1) return a;
            if (term == 2) return b;
            if (term == 3) return c;

            for (int i = 4; i <= term; i++)
            {
                a = a + b + c; if ((1 + 3 * i) % term == 0) { result = a; break; }
                b = a + b + c; if ((2 * i + i - 1) % term == 0) { result = b; break; }
                c = a + b + c; if ((3 * i) % term == 0) { result = c; break; }
            }
            return result;           
        }

But it is somehow not working var res = NTerm_Tribonacci(5);//should be 4 but getting 44

How can I solve this?

Tribonacci Number

shree.pat18 · Accepted Answer · 2014-12-23T06:37:09.223

2

Try this:

private static int NTerm_Tribonacci(int term)
    {
        int a = 0;
        int b = 1;
        int c = 1;
        int result = 0;

        if (term == 0) result = a;
        if (term == 1) result = b;
        if (term == 2) result = c;

        while(term > 2)
        {
            result = a + b + c;
            a = b;
            b = c;
            c = result;
            term--;
        }

        return result;           
    }

Note that as per the definition in your link, I have assumed the first term to be T0, not T1.

Demo

edited Dec 23 '14 at 06:37

answered Dec 23 '14 at 06:30

shree.pat18

21,449
3
43
63

So it does. Please check the demo link I have posted. – shree.pat18 Dec 23 '14 at 06:37
From the definition: "The first few terms for n=0, 1, 2, ... are 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149," So if I call the index of my first term zero, then term five will be 7 and not 4. If you really want to call the first term term 1 rather than term 0, just increment the numbers as required. – shree.pat18 Dec 23 '14 at 06:47

score 1 · Answer 2 · answered Dec 23 '14 at 07:29

I like the "LINQ way" of solving such things:

    public IEnumerable<long> InfiniteTribonacciSequence()
    {
        long a = 0, b = 1, c = 1;
        long nextTerm;

        yield return a;
        yield return b;
        yield return c;

        while (true)
        {
            nextTerm = a + b + c;
            yield return nextTerm;

            a = b;
            b = c;
            c = nextTerm;
        }
    }

But this has to be used carefully, because Methods like Min() will go crazy with this. But you can use e.g. InfiniteTribonacciSequence.Take(5).Last() to get the 5th element of the sequence.

score 0 · Answer 3 · answered Dec 23 '14 at 06:35

0

I think the recursive way is too suitable for such cases:

example:

using System.IO;
using System;

class Program
{
    static void Main()
    {

        int a=4, b;
        b=tribo(a);
        Console.WriteLine(b);
    }

    static public int tribo(int n)
    {
        if(n==0) return 0;
        if(n==1) return 1;
        if(n==2) return 1;
        return(tribo(n-1)+tribo(n-2)+tribo(n-3));
    }
}

this gives the series 0 1 1 2 4 7 13 24 ...

answered Dec 23 '14 at 06:35

chouaib

2,763
5
20
35

I think a recursive solution is not optimal in a language like C# or Java. Check this out: http://stackoverflow.com/questions/21710756/recursion-vs-iteration-fibonacci-sequence – shree.pat18 Dec 23 '14 at 06:39
sorry for the word *suitable*, but I think even *optimal* is not required by the OP, just a working code is sufficient – chouaib Dec 23 '14 at 06:41
Fibonacci is commonly used to show the pitfalls of a simple recursive solution and to introduce memoization as a concept - the only real issue with recursive solutions in C# is that the compiler doesn't support tail call optimization in places that it could, but the common recursive Fibonacci solution isn't tail recursive anyhow. It does, however, hugely benefit from memoization for an n of fairly small magnitude or greater. – Preston Guillot Dec 23 '14 at 06:54

Find the nth element in a tribonacci series

3 Answers3