Sum and Product of all Fibonacci Nodes of a Singly Linked List
Given a singly linked list containing N nodes, the task is to find the sum and product of all the nodes from the list whose data value is a Fibonacci number.
Examples:
Input: LL = 15 -> 16 -> 8 -> 6 -> 13
Output: Sum = 21, Product = 104
Explanation:
The list contains 2 fibonacci data values 8 and 13.
Therefore:
Sum = 8 + 13 = 21
Product = 8 * 13 = 104Input: LL = 5 -> 3 -> 4 -> 2 -> 9
Output: Sum = 10, Product = 30
Explanation:
The list contains 3 fibonacci data values 5, 3 and 2.
Therefore:
Sum = 5 + 3 + 2 = 10
Product = 5 * 3 * 2 = 30
Approach: The idea is to use hashing to precompute and store the Fibonacci numbers, and then check if a node contains a Fibonacci value in O(1) time.
- Traverse through the entire linked list and obtain the maximum value in the list.
- Now, in order to check for the Fibonacci numbers, build a hash table containing all the Fibonacci numbers less than or equal to the maximum value in the linked list.
- Finally, traverse the nodes of the linked list one by one and check if the node contains Fibonacci numbers as their data value. Find the sum and product of the data of the nodes which are Fibonacci.
Below is the implementation of the above approach:
C++
// C++ implementation to find the sum and // product of all of the Fibonacci nodes // in a singly linked list #include <bits/stdc++.h> using namespace std; // Node of the singly linked list struct Node { int data; Node* next; }; // Function to insert a node // at the beginning // of the singly Linked List void push(Node** head_ref, int new_data) { // Allocate new node Node* new_node = (Node*) malloc ( sizeof ( struct Node)); // Insert the data new_node->data = new_data; // Link the old list // to the new node new_node->next = (*head_ref); // Move the head to // point the new node (*head_ref) = new_node; } // Function that returns // the largest element // from the linked list. int largestElement( struct Node* head_ref) { // Declare a max variable // and initialize with INT_MIN int max = INT_MIN; Node* head = head_ref; // Check loop while // head not equal to NULL while (head != NULL) { // If max is less then head->data // then assign value of head->data // to max otherwise // node points to next node. if (max < head->data) max = head->data; head = head->next; } return max; } // Function to create a hash table // to check Fibonacci numbers void createHash(set< int >& hash, int maxElement) { // Inserting the first // two numbers in the hash int prev = 0, curr = 1; hash.insert(prev); hash.insert(curr); // Loop to add Fibonacci numbers upto // the maximum element present in the // linked list while (curr <= maxElement) { int temp = curr + prev; hash.insert(temp); prev = curr; curr = temp; } } // Function to find // the required sum and product void sumAndProduct(Node* head_ref) { // Find the largest node value // in Singly Linked List int maxEle = largestElement(head_ref); // Creating a set containing // all the fibonacci numbers // upto the maximum data value // in the Singly Linked List set< int > hash; createHash(hash, maxEle); int prod = 1; int sum = 0; Node* ptr = head_ref; // Traverse the linked list while (ptr != NULL) { // If current node is fibonacci if (hash.find(ptr->data) != hash.end()) { // Find the sum and the product prod *= ptr->data; sum += ptr->data; } ptr = ptr->next; } cout << "Sum = " << sum << endl; cout << "Product = " << prod; } // Driver code int main() { Node* head = NULL; // Create the linked list // 15 -> 16 -> 8 -> 6 -> 13 push(&head, 13); push(&head, 6); push(&head, 8); push(&head, 16); push(&head, 15); sumAndProduct(head); return 0; } |
Java
// Java implementation to find the sum and // product of all of the Fibonacci nodes // in a singly linked list import java.util.*; class GFG{ // Node of the singly linked list static class Node { int data; Node next; }; // Function to insert a node // at the beginning // of the singly Linked List static Node push(Node head_ref, int new_data) { // Allocate new node Node new_node = new Node(); // Insert the data new_node.data = new_data; // Link the old list // to the new node new_node.next = head_ref; // Move the head to // point the new node head_ref = new_node; return head_ref; } // Function that returns // the largest element // from the linked list. static int largestElement( Node head_ref) { // Declare a max variable // and initialize with Integer.MIN_VALUE int max = Integer.MIN_VALUE; Node head = head_ref; // Check loop while // head not equal to null while (head != null ) { // If max is less then head.data // then assign value of head.data // to max otherwise // node points to next node. if (max < head.data) max = head.data; head = head.next; } return max; } // Function to create a hash table // to check Fibonacci numbers static void createHash(HashSet<Integer> hash, int maxElement) { // Inserting the first // two numbers in the hash int prev = 0 , curr = 1 ; hash.add(prev); hash.add(curr); // Loop to add Fibonacci numbers upto // the maximum element present in the // linked list while (curr <= maxElement) { int temp = curr + prev; hash.add(temp); prev = curr; curr = temp; } } // Function to find // the required sum and product static void sumAndProduct(Node head_ref) { // Find the largest node value // in Singly Linked List int maxEle = largestElement(head_ref); // Creating a set containing // all the fibonacci numbers // upto the maximum data value // in the Singly Linked List HashSet<Integer> hash = new HashSet<Integer>(); createHash(hash, maxEle); int prod = 1 ; int sum = 0 ; Node ptr = head_ref; // Traverse the linked list while (ptr != null ) { // If current node is fibonacci if (hash.contains(ptr.data)) { // Find the sum and the product prod *= ptr.data; sum += ptr.data; } ptr = ptr.next; } System.out.print( "Sum = " + sum + "\n" ); System.out.print( "Product = " + prod); } // Driver code public static void main(String[] args) { Node head = null ; // Create the linked list // 15.16.8.6.13 head = push(head, 13 ); head = push(head, 6 ); head = push(head, 8 ); head = push(head, 16 ); head = push(head, 15 ); sumAndProduct(head); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation to find the sum and # product of all of the Fibonacci nodes # in a singly linked list import sys # Node of the singly linked list class Node(): def __init__( self , data): self .data = data self . next = None # Function to insert a node # at the beginning of the # singly Linked List def push(head_ref, new_data): # Allocate new node new_node = Node(new_data) # Link the old list # to the new node new_node. next = head_ref # Move the head to # point the new node head_ref = new_node return head_ref # Function that returns # the largest element # from the linked list. def largestElement(head_ref): # Declare a max variable # and initialize with INT_MIN max = - sys.maxsize head = head_ref # Check loop while # head not equal to NULL while (head ! = None ): # If max is less then head->data # then assign value of head->data # to max otherwise # node points to next node. if ( max < head.data): max = head.data head = head. next return max # Function to create a hash table # to check Fibonacci numbers def createHash( hash , maxElement): # Inserting the first # two numbers in the hash prev = 0 curr = 1 hash .add(prev) hash .add(curr) # Loop to add Fibonacci numbers upto # the maximum element present in the # linked list while (curr < = maxElement): temp = curr + prev hash .add(temp) prev = curr curr = temp return hash # Function to find the # required sum and product def sumAndProduct(head_ref): # Find the largest node value # in Singly Linked List maxEle = largestElement(head_ref) # Creating a set containing # all the fibonacci numbers # upto the maximum data value # in the Singly Linked List hash = set () hash = createHash( hash , maxEle) prod = 1 sum = 0 ptr = head_ref # Traverse the linked list while (ptr ! = None ): # If current node is fibonacci if ptr.data in hash : # Find the sum and the product prod * = ptr.data sum + = ptr.data ptr = ptr. next print ( "Sum =" , sum ) print ( "Product =" , prod) # Driver code if __name__ = = "__main__" : head = None ; # Create the linked list # 15 -> 16 -> 8 -> 6 -> 13 head = push(head, 13 ) head = push(head, 6 ) head = push(head, 8 ) head = push(head, 16 ) head = push(head, 15 ) sumAndProduct(head) # This code is contributed by rutvik_56 |
C#
// C# implementation to find the sum and // product of all of the Fibonacci nodes // in a singly linked list using System; using System.Collections.Generic; class GFG{ // Node of the singly linked list class Node { public int data; public Node next; }; // Function to insert a node // at the beginning // of the singly Linked List static Node push(Node head_ref, int new_data) { // Allocate new node Node new_node = new Node(); // Insert the data new_node.data = new_data; // Link the old list // to the new node new_node.next = head_ref; // Move the head to // point the new node head_ref = new_node; return head_ref; } // Function that returns // the largest element // from the linked list. static int largestElement( Node head_ref) { // Declare a max variable // and initialize with int.MinValue int max = int .MinValue; Node head = head_ref; // Check loop while // head not equal to null while (head != null ) { // If max is less then head.data // then assign value of head.data // to max otherwise // node points to next node. if (max < head.data) max = head.data; head = head.next; } return max; } // Function to create a hash table // to check Fibonacci numbers static void createHash(HashSet< int > hash, int maxElement) { // Inserting the first // two numbers in the hash int prev = 0, curr = 1; hash.Add(prev); hash.Add(curr); // Loop to add Fibonacci numbers upto // the maximum element present in the // linked list while (curr <= maxElement) { int temp = curr + prev; hash.Add(temp); prev = curr; curr = temp; } } // Function to find // the required sum and product static void sumAndProduct(Node head_ref) { // Find the largest node value // in Singly Linked List int maxEle = largestElement(head_ref); // Creating a set containing // all the fibonacci numbers // upto the maximum data value // in the Singly Linked List HashSet< int > hash = new HashSet< int >(); createHash(hash, maxEle); int prod = 1; int sum = 0; Node ptr = head_ref; // Traverse the linked list while (ptr != null ) { // If current node is fibonacci if (hash.Contains(ptr.data)) { // Find the sum and the product prod *= ptr.data; sum += ptr.data; } ptr = ptr.next; } Console.Write( "Sum = " + sum + "\n" ); Console.Write( "Product = " + prod); } // Driver code public static void Main(String[] args) { Node head = null ; // Create the linked list // 15.16.8.6.13 head = push(head, 13); head = push(head, 6); head = push(head, 8); head = push(head, 16); head = push(head, 15); sumAndProduct(head); } } // This code is contributed by Princi Singh |
Javascript
<script> // javascript implementation to find the sum and // product of all of the Fibonacci nodes // in a singly linked list // Node of the singly linked list class Node { constructor() { this .data = 0; this .next = null ; } } // Function to insert a node // at the beginning // of the singly Linked List function push(head_ref , new_data) { // Allocate new node var new_node = new Node(); // Insert the data new_node.data = new_data; // Link the old list // to the new node new_node.next = head_ref; // Move the head to // point the new node head_ref = new_node; return head_ref; } // Function that returns // the largest element // from the linked list. function largestElement(head_ref) { // Declare a max variable // and initialize with Number.MIN_VALUE var max = Number.MIN_VALUE; var head = head_ref; // Check loop while // head not equal to null while (head != null ) { // If max is less then head.data // then assign value of head.data // to max otherwise // node points to next node. if (max < head.data) max = head.data; head = head.next; } return max; } // Function to create a hash table // to check Fibonacci numbers function createHash( hash , maxElement) { // Inserting the first // two numbers in the hash var prev = 0, curr = 1; hash.add(prev); hash.add(curr); // Loop to add Fibonacci numbers upto // the maximum element present in the // linked list while (curr <= maxElement) { var temp = curr + prev; hash.add(temp); prev = curr; curr = temp; } } // Function to find // the required sum and product function sumAndProduct(head_ref) { // Find the largest node value // in Singly Linked List var maxEle = largestElement(head_ref); // Creating a set containing // all the fibonacci numbers // upto the maximum data value // in the Singly Linked List var hash = new Set(); createHash(hash, maxEle); var prod = 1; var sum = 0; var ptr = head_ref; // Traverse the linked list while (ptr != null ) { // If current node is fibonacci if (hash.has(ptr.data)) { // Find the sum and the product prod *= ptr.data; sum += ptr.data; } ptr = ptr.next; } document.write( "Sum = " + sum + "<br/>" ); document.write( "Product = " + prod); } // Driver code var head = null ; // Create the linked list // 15.16.8.6.13 head = push(head, 13); head = push(head, 6); head = push(head, 8); head = push(head, 16); head = push(head, 15); sumAndProduct(head); // This code contributed by umadevi9616 </script> |
Sum = 21 Product = 104
Time Complexity: O(N), where N is the number of nodes in the linked list.
Auxiliary Space: O(1) because it is using constant space
Contact Us