Find product of nodes whose weights is catalan number in a Linked list
Given a linked list with weights, the task is to find the product of nodes whose weights are Catalan numbers.
Examples:
Input: 3(1) -> 7 (4) -> 5 (2) -> 12 (5) -> 14 (3) -> NULL
Output: 180
Explanation: Catalan number weights are 1, 2, and 5, and the product of their nodes is 3 * 5 * 12 = 180.Input: 45 (4) -> 21 (2) -> 5 (5) -> 42 (3) -> NULL
Output: 110
Explanation: Catalan number weights are 2 and 5, and the product of their nodes is 21 * 5 = 110.
Approach: To solve the problem follow the below Intuition:
The idea behind this approach is to traverse a linked list and calculate the product of nodes that have weights corresponding to Catalan numbers. Catalan numbers are a sequence of natural numbers that often appear in various counting problems, such as the number of different ways to arrange parentheses in a mathematical expression. In this code, the function isCatalan() is used to check if a given number is a Catalan number. The findProduct() function takes the head of the linked list as input and initializes the product to 1. It then iterates through each node in the linked list. If the weight of the current node is a Catalan number, it multiplies the product by the data value of that node. Finally, it returns the computed product.
Follow the steps to solve the problem:
- Define a function named isCatalan it checks whether a given number is a Catalan number. It uses an unordered set to store computed Catalan numbers. The function iteratively calculates Catalan numbers until the current Catalan number exceeds the given number. It checks if the given number is present in the set of computed Catalan numbers and returns true if it is, indicating that the number is a Catalan number.
- Define a function named findProduct it takes the head of a linked list as input and returns the product of nodes with Catalan number weights.
- Initialize a variable product to 1.
- Traverse the linked list starting from the head node. At each node, check if the weight of the node is a Catalan number by calling the isCatalan function. If it is, multiply the current product with the data value of that node.
- Move the current node to the next node in the linked list.
- Repeat steps 4-5 until the end of the linked list is reached (i.e., the current node becomes nullptr).
- Return the final value of product.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Linked List Node struct Node { // Node data int data; // Node weight int weight; // Pointer to next node Node* next; Node( int value, int w) { data = value; weight = w; next = nullptr; } }; // Function to check if a number // is a Catalan number bool isCatalan( int num) { // Set to store computed Catalan // numbers unordered_set< int > catalanNumbers; // Initialize the current Catalan number to 1 int curr = 1; // Initialize a count for tracking the index int count = 1; // Insert the initial Catalan number into the // set catalanNumbers.insert(curr); // Calculate Catalan numbers iteratively // until curr exceeds num while (curr <= num) { // Use the Catalan number formula to // calculate the next Catalan number curr = (curr * 2 * (2 * count - 1)) / (count + 1); // Insert the newly computed Catalan // number into the set catalanNumbers.insert(curr); // Increment the count count++; } // Check if num is in the // set of Catalan numbers return catalanNumbers.count(num); } // Function to find the product of nodes // with Catalan number weights long long findProduct(Node* head) { // Initialize the product to 1 long long product = 1; while (head != nullptr) { // Check if the weight is a // Catalan number if (isCatalan(head->weight)) { // Multiply the product // by the data value product *= head->data; } // Move to the next node in the // linked list head = head->next; } // Return the final product return product; } // Main function int main() { // Create the linked list Node* head = new Node(3, 1); Node* node2 = new Node(7, 4); Node* node3 = new Node(5, 2); Node* node4 = new Node(12, 5); Node* node5 = new Node(14, 3); head->next = node2; node2->next = node3; node3->next = node4; node4->next = node5; // Find the product of nodes // with Catalan number weights long long product = findProduct(head); // Display the result cout << "Product of nodes with Catalan number weights: " << product << endl; return 0; } |
Java
import java.util.HashSet; import java.util.Set; // Linked List Node class Node { // Node data int data; // Node weight int weight; // Pointer to next node Node next; Node( int value, int w) { data = value; weight = w; next = null ; } } public class Main { // Function to check if a number is a Catalan number static boolean isCatalan( int num) { // Set to store computed Catalan numbers Set<Integer> catalanNumbers = new HashSet<>(); // Initialize the current Catalan number to 1 int curr = 1 ; // Initialize a count for tracking the index int count = 1 ; // Insert the initial Catalan number into the set catalanNumbers.add(curr); // Calculate Catalan numbers iteratively until curr exceeds num while (curr <= num) { // Use the Catalan number formula to calculate the next Catalan number curr = (curr * 2 * ( 2 * count - 1 )) / (count + 1 ); // Insert the newly computed Catalan number into the set catalanNumbers.add(curr); // Increment the count count++; } // Check if num is in the set of Catalan numbers return catalanNumbers.contains(num); } // Function to find the product of nodes with Catalan number weights static long findProduct(Node head) { // Initialize the product to 1 long product = 1 ; while (head != null ) { // Check if the weight is a Catalan number if (isCatalan(head.weight)) { // Multiply the product by the data value product *= head.data; } // Move to the next node in the linked list head = head.next; } // Return the final product return product; } // Main function public static void main(String[] args) { // Create the linked list Node head = new Node( 3 , 1 ); Node node2 = new Node( 7 , 4 ); Node node3 = new Node( 5 , 2 ); Node node4 = new Node( 12 , 5 ); Node node5 = new Node( 14 , 3 ); head.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; // Find the product of nodes with Catalan number weights long product = findProduct(head); // Display the result System.out.println( "Product of nodes with Catalan number weights: " + product); } } |
Python3
class Node: def __init__( self , value, w): self .data = value self .weight = w self . next = None def is_catalan(num): # Set to store computed Catalan numbers catalan_numbers = set () # Initialize the current Catalan number to 1 curr = 1 # Initialize a count for tracking the index count = 1 # Insert the initial Catalan number into the set catalan_numbers.add(curr) # Calculate Catalan numbers iteratively until curr exceeds num while curr < = num: # Use the Catalan number formula to calculate the next Catalan number curr = (curr * 2 * ( 2 * count - 1 )) / / (count + 1 ) # Insert the newly computed Catalan number into the set catalan_numbers.add(curr) # Increment the count count + = 1 # Check if num is in the set of Catalan numbers return num in catalan_numbers def find_product(head): # Initialize the product to 1 product = 1 current = head while current is not None : # Check if the weight is a Catalan number if is_catalan(current.weight): # Multiply the product by the data value product * = current.data # Move to the next node in the linked list current = current. next # Return the final product return product # Main function if __name__ = = "__main__" : # Create the linked list head = Node( 3 , 1 ) node2 = Node( 7 , 4 ) node3 = Node( 5 , 2 ) node4 = Node( 12 , 5 ) node5 = Node( 14 , 3 ) head. next = node2 node2. next = node3 node3. next = node4 node4. next = node5 # Find the product of nodes with Catalan number weights product = find_product(head) # Display the result print ( "Product of nodes with Catalan number weights:" , product) |
C#
using System; using System.Collections.Generic; // Linked List Node class Node { // Node data public int data; // Node weight public int weight; // Pointer to next node public Node next; public Node( int value, int w) { data = value; weight = w; next = null ; } } class Program { // Function to check if a number // is a Catalan number static bool IsCatalan( int num) { // Set to store computed Catalan // numbers HashSet< int > catalanNumbers = new HashSet< int >(); // Initialize the current Catalan number to 1 int curr = 1; // Initialize a count for tracking the index int count = 1; // Insert the initial Catalan number into the // set catalanNumbers.Add(curr); // Calculate Catalan numbers iteratively // until curr exceeds num while (curr <= num) { // Use the Catalan number formula to // calculate the next Catalan number curr = (curr * 2 * (2 * count - 1)) / (count + 1); // Insert the newly computed Catalan // number into the set catalanNumbers.Add(curr); // Increment the count count++; } // Check if num is in the // set of Catalan numbers return catalanNumbers.Contains(num); } // Function to find the product of nodes // with Catalan number weights static long FindProduct(Node head) { // Initialize the product to 1 long product = 1; while (head != null ) { // Check if the weight is a // Catalan number if (IsCatalan(head.weight)) { // Multiply the product // by the data value product *= head.data; } // Move to the next node in the // linked list head = head.next; } // Return the final product return product; } // Main function static void Main() { // Create the linked list Node head = new Node(3, 1); Node node2 = new Node(7, 4); Node node3 = new Node(5, 2); Node node4 = new Node(12, 5); Node node5 = new Node(14, 3); head.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; // Find the product of nodes // with Catalan number weights long product = FindProduct(head); // Display the result Console.WriteLine( "Product of nodes with Catalan number weights: " + product); } } |
Javascript
// JavaScript code for the above approach: // Linked List Node class Node { // Constructor to initialize the node with data and weight constructor(value, w) { this .data = value; this .weight = w; this .next = null ; } } // Function to check if a number is a Catalan number function isCatalan(num) { // Set to store computed Catalan numbers const catalanNumbers = new Set(); // Initialize the current Catalan number to 1 let curr = 1; // Initialize a count for tracking the index let count = 1; // Insert the initial Catalan number // into the set catalanNumbers.add(curr); // Calculate Catalan numbers iteratively // until curr exceeds num while (curr <= num) { // Use the Catalan number formula to // calculate the next Catalan number curr = (curr * 2 * (2 * count - 1)) / (count + 1); // Insert the newly computed Catalan // number into the set catalanNumbers.add(curr); // Increment the count count++; } // Check if num is in the set // of Catalan numbers return catalanNumbers.has(num); } // Function to find the product of nodes // with Catalan number weights function findProduct(head) { // Initialize the product to 1 let product = 1; while (head !== null ) { // Check if the weight is a // Catalan number if (isCatalan(head.weight)) { // Multiply the product by // the data value product *= head.data; } // Move to the next node in the linked list head = head.next; } // Return the final product return product; } // Driver Code // Create the linked list const head = new Node(3, 1); const node2 = new Node(7, 4); const node3 = new Node(5, 2); const node4 = new Node(12, 5); const node5 = new Node(14, 3); head.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; // Find the product of nodes with // Catalan number weights const product = findProduct(head); // Display the result console.log( "Product of nodes with Catalan number weights: " + product); |
Product of nodes with Catalan number weights: 180
Time Complexity: O(n), where n is the number of nodes in the linked list, because we are iterating through each node once.
Auxiliary Space: O(log(num)), where num is the weight of the node with the maximum weight, because we are uses an unordered set to store computed Catalan numbers, which can grow up to log(num) elements.