Find the Kth Largest Tribonacci Number Node in a Singly Linked List
Given a singly linked list containing integers, the task is to find the Kth largest Tribonacci number in the linked list.
Note: A Tribonacci number is a series of numbers where each number is the sum of the three preceding numbers.
The Tribonacci Sequence: 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768…….
Examples:
Input: 12 -> 4 -> 9 -> 3 -> 0 -> 25 -> 13 -> NULL, K = 2
Output: 4
Explanation: The Tribonacci number Nodes in the given linked list are 4, 0, 13, and the Kth largest is 4.Input: 144 -> 111 -> 44 -> 81 -> 1 -> 15 -> 149 -> 0 -> NULL, K = 4
Output: 1
Explanation: The Tribonacci number Nodes in the given linked list are 44, 81, 1, 149, 0, and the Kth largest is 1.
Approach: To solve the problem follow the below idea:
The intuition behind this approach is to efficiently find the Kth largest Tribonacci number in a linked list by maintaining a min-heap (priority queue) of size K. We traverse the linked list, checking each node to see if it is a Tribonacci number. If it is, we compare it with the smallest number in the min-heap. If the current Tribonacci number is larger, we replace the smallest number in the min-heap. This process ensures that the min-heap always contains the K largest Tribonacci numbers encountered in the linked list. As a result, the top element of the min-heap will be the Kth largest Tribonacci number when the traversal is complete.
Steps of this approach:
- Define a priority queue (min-heap) to maintain the K smallest Tribonacci numbers encountered.
- Create a helper function to check if a number is a Tribonacci number by iterating through the Tribonacci sequence.
- Traverse the linked list, examining each node’s value.
- For each node, check if it is a Tribonacci number using the helper function.
- If it is a Tribonacci number, add it to the priority queue.
- If the priority queue size exceeds K, remove the smallest element.
- Continue this process until you have processed all nodes in the linked list.
- At the end of the traversal, the priority queue will contain the K largest Tribonacci numbers.
- Return the top element of the priority queue, which represents the Kth largest Tribonacci number.
Implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Define the singly linked list node structure struct ListNode { int val; ListNode* next; ListNode( int x) : val(x) , next(nullptr) { } }; // Function to find the Kth largest Tribonacci number int findKthLargestTribonacci(ListNode* head, int K) { // Create a min-heap to keep track of the K smallest // Tribonacci numbers priority_queue< int , vector< int >, greater< int > > minHeap; // Helper function to check if a number is a Tribonacci // number auto isTribonacci = []( int num) { int a = 0, b = 1, c = 1; while (c <= num) { if (c == num) { return true ; } int temp = a + b + c; a = b; b = c; c = temp; } return false ; }; // Traverse the linked list and maintain a min-heap of // size K ListNode* current = head; while (current) { if (isTribonacci(current->val)) { minHeap.push(current->val); // If the min-heap size exceeds K, remove the // smallest element if (minHeap.size() > K) { minHeap.pop(); } } current = current->next; } // Return the top element of the min-heap, representing // the Kth largest Tribonacci number return minHeap .top(); // Assuming K is always within bounds } int main() { // Create the first sample linked list ListNode* head1 = new ListNode(12); head1->next = new ListNode(4); head1->next->next = new ListNode(9); head1->next->next->next = new ListNode(3); head1->next->next->next->next = new ListNode(0); head1->next->next->next->next->next = new ListNode(25); head1->next->next->next->next->next->next = new ListNode(13); int K1 = 2; int result1 = findKthLargestTribonacci(head1, K1); cout << "The " << K1 << "th largest Tribonacci number is: " << result1 << endl; // Create the second sample linked list ListNode* head2 = new ListNode(144); head2->next = new ListNode(111); head2->next->next = new ListNode(44); head2->next->next->next = new ListNode(81); head2->next->next->next->next = new ListNode(1); head2->next->next->next->next->next = new ListNode(15); head2->next->next->next->next->next->next = new ListNode(149); head2->next->next->next->next->next->next->next = new ListNode(0); int K2 = 4; int result2 = findKthLargestTribonacci(head2, K2); cout << "The " << K2 << "th largest Tribonacci number is: " << result2 << endl; return 0; } |
Java
import java.util.PriorityQueue; // Define the singly linked list node structure class ListNode { int val; ListNode next; public ListNode( int x) { val = x; next = null ; } } public class TribonacciLinkedList { // Function to find the Kth largest Tribonacci number public static int findKthLargestTribonacci(ListNode head, int K) { // Create a min-heap to keep track of the K smallest Tribonacci numbers PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // Helper function to check if a number is a Tribonacci number // The lambda expression (isTribonacci) is used as a predicate // to test if a given number is a Tribonacci number // The predicate is used later in the code to filter Tribonacci numbers java.util.function.Predicate<Integer> isTribonacci = num -> { int a = 0 , b = 1 , c = 1 ; while (c <= num) { if (c == num) { return true ; } int temp = a + b + c; a = b; b = c; c = temp; } return false ; }; // Traverse the linked list and maintain a min-heap of size K ListNode current = head; while (current != null ) { if (isTribonacci.test(current.val)) { minHeap.add(current.val); // If the min-heap size exceeds K, remove the smallest element if (minHeap.size() > K) { minHeap.poll(); } } current = current.next; } // Return the top element of the min-heap, representing the Kth largest Tribonacci number return minHeap.peek(); // Assuming K is always within bounds } public static void main(String[] args) { // Create the first sample linked list ListNode head1 = new ListNode( 12 ); head1.next = new ListNode( 4 ); head1.next.next = new ListNode( 9 ); head1.next.next.next = new ListNode( 3 ); head1.next.next.next.next = new ListNode( 0 ); head1.next.next.next.next.next = new ListNode( 25 ); head1.next.next.next.next.next.next = new ListNode( 13 ); int K1 = 2 ; int result1 = findKthLargestTribonacci(head1, K1); System.out.println( "The " + K1 + "th largest Tribonacci number is: " + result1); // Create the second sample linked list ListNode head2 = new ListNode( 144 ); head2.next = new ListNode( 111 ); head2.next.next = new ListNode( 44 ); head2.next.next.next = new ListNode( 81 ); head2.next.next.next.next = new ListNode( 1 ); head2.next.next.next.next.next = new ListNode( 15 ); head2.next.next.next.next.next.next = new ListNode( 149 ); head2.next.next.next.next.next.next.next = new ListNode( 0 ); int K2 = 4 ; int result2 = findKthLargestTribonacci(head2, K2); System.out.println( "The " + K2 + "th largest Tribonacci number is: " + result2); } } |
Python3
import heapq class ListNode: def __init__( self , x): self .val = x self . next = None def find_kth_largest_tribonacci(head, K): min_heap = [] def is_tribonacci(num): a, b, c = 0 , 1 , 1 while c < = num: if c = = num: return True temp = a + b + c a, b, c = b, c, temp return False current = head while current: if is_tribonacci(current.val): heapq.heappush(min_heap, current.val) if len (min_heap) > K: heapq.heappop(min_heap) current = current. next return min_heap[ 0 ] if min_heap else None if __name__ = = "__main__" : # Create the first sample linked list head1 = ListNode( 12 ) head1. next = ListNode( 4 ) head1. next . next = ListNode( 9 ) head1. next . next . next = ListNode( 3 ) head1. next . next . next . next = ListNode( 0 ) head1. next . next . next . next . next = ListNode( 25 ) head1. next . next . next . next . next . next = ListNode( 13 ) K1 = 2 result1 = find_kth_largest_tribonacci(head1, K1) print (f "The {K1}th largest Tribonacci number is: {result1}" ) # Create the second sample linked list head2 = ListNode( 144 ) head2. next = ListNode( 111 ) head2. next . next = ListNode( 44 ) head2. next . next . next = ListNode( 81 ) head2. next . next . next . next = ListNode( 1 ) head2. next . next . next . next . next = ListNode( 15 ) head2. next . next . next . next . next . next = ListNode( 149 ) head2. next . next . next . next . next . next . next = ListNode( 0 ) K2 = 4 result2 = find_kth_largest_tribonacci(head2, K2) print (f "The {K2}th largest Tribonacci number is: {result2}" ) # code is contributed by shinjanpatra |
C#
using System; using System.Collections.Generic; // Define the singly linked list node structure public class ListNode { public int val; public ListNode next; public ListNode( int x) { val = x; next = null ; } } class Program { // Function to find the Kth largest Tribonacci number static int FindKthLargestTribonacci(ListNode head, int K) { // Create a min-heap to keep track of the K smallest // Tribonacci numbers var minHeap = new SortedSet< int >(); // Helper function to check if a number is a Tribonacci // number Func< int , bool > isTribonacci = num => { int a = 0, b = 1, c = 1; while (c <= num) { if (c == num) return true ; int temp = a + b + c; a = b; b = c; c = temp; } return false ; }; // Traverse the linked list and maintain a min-heap of // size K ListNode current = head; while (current != null ) { if (isTribonacci(current.val)) { minHeap.Add(current.val); // If the min-heap size exceeds K, remove the // smallest element if (minHeap.Count > K) minHeap.Remove(minHeap.Min); } current = current.next; } // Return the top element of the min-heap, representing // the Kth largest Tribonacci number return minHeap.Min; // Assuming K is always within bounds } static void Main() { // Create the first sample linked list ListNode head1 = new ListNode(12) { next = new ListNode(4) { next = new ListNode(9) { next = new ListNode(3) { next = new ListNode(0) { next = new ListNode(25) { next = new ListNode(13) } } } } } }; int K1 = 2; int result1 = FindKthLargestTribonacci(head1, K1); Console.WriteLine($ "The {K1}th largest Tribonacci number is: {result1}" ); // Create the second sample linked list ListNode head2 = new ListNode(144) { next = new ListNode(111) { next = new ListNode(44) { next = new ListNode(81) { next = new ListNode(1) { next = new ListNode(15) { next = new ListNode(149) { next = new ListNode(0) } } } } } } }; int K2 = 4; int result2 = FindKthLargestTribonacci(head2, K2); Console.WriteLine($ "The {K2}th largest Tribonacci number is: {result2}" ); } } |
Javascript
// Define the singly linked list node structure class ListNode { constructor(x) { this .val = x; this .next = null ; } } // Function to find the Kth largest Tribonacci number function findKthLargestTribonacci(head, K) { // Create a min-heap to keep track of the K smallest Tribonacci numbers const minHeap = new Set(); // Helper function to check if a number is a Tribonacci number const isTribonacci = (num) => { let a = 0, b = 1, c = 1; while (c <= num) { if (c === num) { return true ; } const temp = a + b + c; a = b; b = c; c = temp; } return false ; }; // Traverse the linked list and maintain a min-heap of size K let current = head; while (current !== null ) { if (isTribonacci(current.val)) { minHeap.add(current.val); // If the min-heap size exceeds K, remove the smallest element if (minHeap.size > K) { const minValue = Math.min(...minHeap); minHeap. delete (minValue); } } current = current.next; } // Return the smallest element in the min-heap, representing the Kth largest Tribonacci number return Math.min(...minHeap); // Assuming K is always within bounds } // Create the first sample linked list const head1 = new ListNode(12); head1.next = new ListNode(4); head1.next.next = new ListNode(9); head1.next.next.next = new ListNode(3); head1.next.next.next.next = new ListNode(0); head1.next.next.next.next.next = new ListNode(25); head1.next.next.next.next.next.next = new ListNode(13); const K1 = 2; const result1 = findKthLargestTribonacci(head1, K1); console.log(`The ${K1}th largest Tribonacci number is: ${result1}`); // Create the second sample linked list const head2 = new ListNode(144); head2.next = new ListNode(111); head2.next.next = new ListNode(44); head2.next.next.next = new ListNode(81); head2.next.next.next.next = new ListNode(1); head2.next.next.next.next.next = new ListNode(15); head2.next.next.next.next.next.next = new ListNode(149); head2.next.next.next.next.next.next.next = new ListNode(0); const K2 = 4; const result2 = findKthLargestTribonacci(head2, K2); console.log(`The ${K2}th largest Tribonacci number is: ${result2}`); |
The 2th largest Tribonacci number is: 4 The 4th largest Tribonacci number is: 1
Time Complexity: O(n*log K), It’s linear in the number of nodes (n) in the linked list, but the min-heap operations have a logarithmic time complexity in terms of K.
Auxiliary Space: O(K), The code uses a min-heap with a maximum size of K, and the space required depends on K, which is a constant space requirement.