Hope you are having a great day. Apparently I had too much to say out of topic in my last post. Thanks for the message. I will keep it short.
During the workdays my wife prepares lunch while I work in my office. On occasions she asked me to fire the grill to cook the meal. We try to make enough food over the weekends so there are enough leftovers to simplify the process on workdays. That said, it seems that today would have been a great day to grill outside. The morning started at 56 F and the forecast calls for 77 F for a high. The day will be sunny. It seems that it is going to be a perfect day.
I picked from LeetCode problem 1137 N-th Tribonacci Number. For the name, it seems like a possible recursive problem similar to generating a Fibonacci number. Looked up in my blog and there are a few posts related to Fibonacci numbers. I guess that Fibonacci Sequence is the most appropriate.
The Tribonacci sequence Tn is defined as follows: T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0. Given n, return the value of Tn.
It seems that LeetCode has defined the problem nicely. In a nutshell, instead to add the two previous values to generate the current one, we need to add the three previous values, hence the clever name Tribonacci.
public int tribonacci(int n) {
}
It seems that given an integer we just have to return the Tribonacci associated with it.
I prefer to tackle problems using my own environment. Because of that I need to generate the test scaffolding. In this particular problem we just need to collect the number and pass it to the function we need to implement.
4 main <<< N: 4 main <<< n: 4 Tn: 4 main <<< n: 4 Tn: 4 main <<< n: 4 Tn: 4 main <<< n: 4 Tn: 4 3 main <<< N: 3 main <<< n: 3 Tn: 2 main <<< n: 3 Tn: 2 main <<< n: 3 Tn: 2 main <<< n: 3 Tn: 2 5 main <<< N: 5 main <<< n: 5 Tn: 7 main <<< n: 5 Tn: 7 main <<< n: 5 Tn: 7 main <<< n: 5 Tn: 7 0 main <<< N: 0 main <<< n: 0 Tn: 0 main <<< n: 0 Tn: 0 main <<< n: 0 Tn: 0 main <<< n: 0 Tn: 0 1 main <<< N: 1 main <<< n: 1 Tn: 1 main <<< n: 1 Tn: 1 main <<< n: 1 Tn: 1 main <<< n: 1 Tn: 1 2 main <<< N: 2 main <<< n: 2 Tn: 1 main <<< n: 2 Tn: 1 main <<< n: 2 Tn: 1 main <<< n: 2 Tn: 1 25 main <<< N: 25 main <<< n: 25 Tn: 1389537 main <<< n: 25 Tn: 1389537 main <<< n: 25 Tn: 1389537 main <<< n: 25 Tn: 1389537 37 main <<< N: 37 main <<< n: 37 Tn: 2082876103 main <<< n: 37 Tn: 2082876103 main <<< n: 37 Tn: 2082876103 main <<< n: 37 Tn: 2082876103
This is the output of the test scaffolding for different runs. It appears that we need to enter the number to call the function and the function returns the associated value which we display. That said, it seems that we have four 
different approaches to compute the result. This will become obvious as soon as we see the test scaffolding.
Note that the first few numbers in the sequence are:
0, 1, 1, 2, 4, 7, 12, 24, …
This implies that if we call the tribonacci() function with n = 0, we should get in return a 0, and it seems we do. If we enter a 1, the result should be 1. If we enter 2 the result should also be 1. We just need to add the previous three values in the sequence.
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read N ****
int N = sc.nextInt();
// ???? ????
System.out.println("main <<< N: " + N);
// **** close scanner ****
sc.close();
// **** loop generating Tn ****
// for (int n = 0; n <= N; n++) {
for (int n = N; n <= N; n++) {
// **** generate and display Tn ****
System.out.println("main <<< n: " + n + " Tn: " + tribonacci(n));
// **** generate and display Tn (recursive; but slow) ****
System.out.println("main <<< n: " + n + " Tn: " + tribonacci1(n));
// **** generate and display Tn (iterative) ****
System.out.println("main <<< n: " + n + " Tn: " + tribonacci2(n));
// **** generate and display Tn (recursive) ****
System.out.println("main <<< n: " + n + " Tn: " + tribonacci3(n));
}
}
The test scaffolding is only required if you want to test the code on your computer. We open a scanner, read and display a value and then close the scanner. We then enter a loop. Note that I have defeated the loop by starting at N and ending at the same value. It is nice to check the entire set automatically but it generates a lot of output. For this reason I changed the initial value for n in the loop.
It seems we have four approaches. They all work but the second seems to be too slow to be accepted by LeetCode. If you change the initial value in the loop and set it to 1, then specify a larger N (I do not check it in the code but you can deduct it from the requirements), then the program will display sets of four numbers which should match (and as far as I can tell they do).
/**
* Given n, return the value of Tn.
* Requires array initialization.
*/
static int tribonacci(int n) {
// **** initialization ****
int[] t = {0, 1, 1, 0};
// **** recursive case ****
return tribRec(n, t);
}
If I am not mistaken, this function was accepted by LeetCode. It uses a small array and then calls a recursive function. I wanted to use a recursive approach because the problem is tagged as recursive.
/**
* Given n, return the value of Tn.
* Recursive call.
*/
static int tribRec(int n, int[] t) {
// **** base case ****
if (n <= 2) {
return t[n];
}
// **** update the array ****
t[3] = t[0] + t[1] + t[2];
t[0] = t[1];
t[1] = t[2];
t[2] = t[3];
// **** recursive case (just a counter) ****
tribRec(n - 1, t);
// **** return tribonacci of n ****
return t[2];
}
This is the recursive call used by the previous function. It has a base case followed by the computation of the current tribonacci number which is stored in the last element of the array. The previous values in the sequence are then updated. Once that is done, we recursively call the function passing the next lowest integer and the array.
When all is set and done, we return the tribonacci of n.
/**
* Given n, return the value of Tn.
* Does not require external data.
* This function is recursive.
*/
static int tribonacci1(int n) {
// **** base case(s) ****
if (n == 0)
return 0;
if ((n == 1) || (n == 2))
return 1;
// **** recursive case ****
return tribonacci1(n - 1) + tribonacci1(n - 2) + tribonacci1(n - 3);
}
This seems to be the simplest and most elegant solution so far. The problem, as with most recursive calls, is that they take time and consume stack memory. When I run it in my computer I can see the delay when the initial n gets closer to 37 (which is the required upper bound for the problem). I did submit this solution but it timed out on LeetCode.
/**
* Given n, return the value of Tn.
* Require internal data.
* This function is iterative.
*/
static int tribonacci2(int n) {
// **** base cases ****
if (n == 0)
return 0;
if ((n == 1) || (n == 2))
return 1;
// **** to hold tribonacci sequence ****
int[] t = new int[n + 1];
// **** initialize array ****
t[0] = 0;
t[1] = t[2] = 1;
// **** loop generating the next value ****
for (int i = 3; i <= n; i++) {
t[i] = t[i - 1] + t[i - 2] + t[i - 3];
}
// **** return the requested value ****
return t[n];
}
This is an iterative function. We first check for the simple cases. Then we declare an array and initialize it as needed. We are now ready to loop generating the tribonacci numbers. When done with the loop, we return the expected value.
/**
* Given n, return the value of Tn.
* This is an initialization function.
*/
static int tribonacci3(int n) {
// **** ****
int[] arr = new int[n + 1];
// **** recursive call (using a array) ****
trib(n, arr);
// **** return tribonacci of n ****
return arr[n];
}
This is an initialization function. We also declare an integer array. We then call a recursive function. When done, we return the expected result. If you just copy the contents of this function in LeetCode and add the following complete function, LeetCode should accept it. It did it for me.
/**
* Given n, return the value of Tn.
* This function is recursive.
*/
static void trib(int n, int[] arr) {
// **** base cases ****
if (n == 0)
arr[n] = 0;
if ((n == 1) || (n == 2))
arr[n] = 1;
// **** recurse (if needed) ****
if (n > 0) {
// **** recursive call ****
trib(n - 1, arr);
// **** compute current tribonacci element ****
if (n >= 3)
arr[n] = arr[n - 1] + arr[n - 2] + arr[n - 3];
}
}
This is the recursive function that is called by the previous one. I guess you can come up with lots of approaches. I was experimenting with using a stack, but shortly after gave up given that a stack is more expensive and slower to use than an array. That said; if inclined you can give it a try and perhaps compare the execution times with other approaches.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 1766 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa