Horje
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}`);

Output

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.


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Find the Largest Number Using Four Nodes in a Singly Linked List Find the Largest Number Using Four Nodes in a Singly Linked List
Replace every node with closest Prime number in a Singly Linked List Replace every node with closest Prime number in a Singly Linked List
Move the Kth Largest Fibonacci Number Node to the End of a Singly Linked List Move the Kth Largest Fibonacci Number Node to the End of a Singly Linked List
Find the Absolute Difference between the Right View Sum of two Binary Trees Find the Absolute Difference between the Right View Sum of two Binary Trees
Max count of items that can be removed from the Array without changing the mode Max count of items that can be removed from the Array without changing the mode

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 15



 

Horje