Sum and Product of all Fibonacci Nodes of a Singly Linked List | C ++ implementation to find the sum and product of all of the Fibonacci nodes in a singly linked list ; Node of the singly linked list ; Function to insert a node at the beginning of the singly Linked List ; Allocate new node ; Insert the data ; Link the old list to the new node ; Move the head to point the new node ; Function that returns the largest element from the linked list . ; Declare a max variable and initialize with INT_MIN ; Check loop while head not equal to NULL ; If max is less then head -> data then assign value of head -> data to max otherwise node points to next node . ; Function to create a hash table to check Fibonacci numbers ; Inserting the first two numbers in the hash ; Loop to add Fibonacci numbers upto the maximum element present in the linked list ; Function to find the required sum and product ; Find the largest node value in Singly Linked List ; Creating a set containing all the fibonacci numbers upto the maximum data value in the Singly Linked List ; Traverse the linked list ; If current node is fibonacci ; Find the sum and the product ; Driver code ; Create the linked list 15 -> 16 -> 8 -> 6 -> 13
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * next ; } ; void push ( Node * * head_ref , int new_data ) { Node * new_node = ( Node * ) malloc ( sizeof ( struct Node ) ) ; new_node -> data = new_data ; new_node -> next = ( * head_ref ) ; ( * head_ref ) = new_node ; } int largestElement ( struct Node * head_ref ) { int max = INT_MIN ; Node * head = head_ref ; while ( head != NULL ) { if ( max < head -> data ) max = head -> data ; head = head -> next ; } return max ; } void createHash ( set < int > & hash , int maxElement ) { int prev = 0 , curr = 1 ; hash . insert ( prev ) ; hash . insert ( curr ) ; while ( curr <= maxElement ) { int temp = curr + prev ; hash . insert ( temp ) ; prev = curr ; curr = temp ; } } void sumAndProduct ( Node * head_ref ) { int maxEle = largestElement ( head_ref ) ; set < int > hash ; createHash ( hash , maxEle ) ; int prod = 1 ; int sum = 0 ; Node * ptr = head_ref ; while ( ptr != NULL ) { if ( hash . find ( ptr -> data ) != hash . end ( ) ) { prod *= ptr -> data ; sum += ptr -> data ; } ptr = ptr -> next ; } cout << " Sum ▁ = ▁ " << sum << endl ; cout << " Product ▁ = ▁ " << prod ; } int main ( ) { Node * head = NULL ; push ( & head , 13 ) ; push ( & head , 6 ) ; push ( & head , 8 ) ; push ( & head , 16 ) ; push ( & head , 15 ) ; sumAndProduct ( head ) ; return 0 ; }