Skip to content

Commit 82808e5

Browse files
cheehwatangcheehwatang
authored
Merge pull request #326 from cheehwatang/add-1137-N-thTribonacciNumber
Add 1137. N-th Tribonacci Number (Iterative)
2 parents 48fc241 + 6613325 commit 82808e5

File tree

2 files changed

+71
-13
lines changed

2 files changed

+71
-13
lines changed

‎README.md

Lines changed: 38 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,18 @@
2727
<th>Solution</th>
2828
<th>Topics</th>
2929
</tr>
30+
<tr>
31+
<td align="center">September 5th</td>
32+
<td>1137. <a href="https://leetcode.com/problems/n-th-tribonacci-number/">N-th Tribonacci Number</a></td>
33+
<td align="center">$\text{\color{TealBlue}Easy}$</td>
34+
<td align="center">
35+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/1137.%20N-th%20Tribonacci%20Number/NthTribonacciNumber_Iterative.java">Dynamic Programming</a>
36+
</td>
37+
<td align="center">
38+
<a href="#dynamic-programming">Dynamic Programming</a>,
39+
<a href="#math">Math</a>
40+
</td>
41+
</tr>
3042
<tr>
3143
<td align="center">September 4th</td>
3244
<td>923. <a href="https://leetcode.com/problems/3sum-with-multiplicity/">3Sum With Multiplicity</a></td>
@@ -77,19 +89,6 @@
7789
<a href="#two-pointers">Two Pointers</a>
7890
</td>
7991
</tr>
80-
<tr>
81-
<td align="center">August 31st</td>
82-
<td>15. <a href="https://leetcode.com/problems/3sum/">3Sum</a></td>
83-
<td align="center">$\text{\color{Dandelion}Medium}$</td>
84-
<td align="center">
85-
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/15.%203Sum/ThreeSum.java">Sorting & Two Pointers</a>
86-
</td>
87-
<td align="center">
88-
<a href="#array">Array</a>,
89-
<a href="#sorting">Sorting</a>,
90-
<a href="#two-pointers">Two Pointers</a>
91-
</td>
92-
</tr>
9392
</table>
9493
</br>
9594
<hr>
@@ -4327,6 +4326,19 @@
43274326
</td>
43284327
<td></td>
43294328
</tr>
4329+
<tr>
4330+
<td align="center">1137</td>
4331+
<td><a href="https://leetcode.com/problems/n-th-tribonacci-number/">N-th Tribonacci Number</a></td>
4332+
<td align="center">
4333+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/1137.%20N-th%20Tribonacci%20Number/NthTribonacciNumber_Iterative.java">Java</a>
4334+
</td>
4335+
<td align="center">$\text{\color{TealBlue}Easy}$</td>
4336+
<td align="center">
4337+
<a href="#dynamic-programming">Dynamic Programming</a>,
4338+
<a href="#math">Math</a>
4339+
</td>
4340+
<td></td>
4341+
</tr>
43304342
<tr>
43314343
<td align="center">1578</td>
43324344
<td><a href="https://leetcode.com/problems/minimum-time-to-make-rope-colorful/">Minimum Time to Make Rope Colorful</a></td>
@@ -6258,6 +6270,19 @@
62586270
</td>
62596271
<td></td>
62606272
</tr>
6273+
<tr>
6274+
<td align="center">1137</td>
6275+
<td><a href="https://leetcode.com/problems/n-th-tribonacci-number/">N-th Tribonacci Number</a></td>
6276+
<td align="center">
6277+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/1137.%20N-th%20Tribonacci%20Number/NthTribonacciNumber_Iterative.java">Java</a>
6278+
</td>
6279+
<td align="center">$\text{\color{TealBlue}Easy}$</td>
6280+
<td align="center">
6281+
<a href="#dynamic-programming">Dynamic Programming</a>,
6282+
<a href="#math">Math</a>
6283+
</td>
6284+
<td></td>
6285+
</tr>
62616286
<tr>
62626287
<td align="center">1154</td>
62636288
<td><a href="https://leetcode.com/problems/day-of-the-year/">Day of the Year</a></td>

‎solutions/1137. N-th Tribonacci Number/NthTribonacciNumber_Iterative.java

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package com.cheehwatang.leetcode;
2+
3+
// Time Complexity : O(n),
4+
// where 'n' is the input 'n'.
5+
// We traverse from 3 to 'n' to calculate the n-th tribonacci number.
6+
//
7+
// Space Complexity : O(1),
8+
// as the auxiliary space used is independent of the input.
9+
10+
public class NthTribonacciNumber_Iterative {
11+
12+
// Approach:
13+
// We use the iterative method, using the variable 'first', 'second' and 'third' to keep track.
14+
15+
public int tribonacci(int n) {
16+
if (n == 0 || n == 1) return n;
17+
if (n == 2) return 1;
18+
19+
// As we need both 'n - 1', 'n - 2' and 'n - 3' to start, record 'first', 'second' and 'third', respectively.
20+
// For each iteration until n, sum all three numbers and replace the numbers.
21+
int first = 1;
22+
int second = 1;
23+
int third = 0;
24+
int result = 0;
25+
for (int i = 3; i <= n; i++) {
26+
result = first + second + third;
27+
third = second;
28+
second = first;
29+
first = result;
30+
}
31+
return result;
32+
}
33+
}

0 commit comments

Comments
 (0)