Dada una lista enlazada individualmente que contiene N Nodes, la tarea es encontrar la suma y el producto de todos los Nodes de la lista cuyo valor de datos es un número de Fibonacci.
Ejemplos:
Entrada: LL = 15 -> 16 -> 8 -> 6 -> 13
Salida: Suma = 21, Producto = 104
Explicación:
La lista contiene 2 valores de datos de fibonacci 8 y 13.
Por lo tanto:
Suma = 8 + 13 = 21
Producto = 8 * 13 = 104Entrada: LL = 5 -> 3 -> 4 -> 2 -> 9
Salida: Suma = 10, Producto = 30
Explicación:
La lista contiene 3 valores de datos de Fibonacci 5, 3 y 2.
Por lo tanto:
Suma = 5 + 3 + 2 = 10
Producto = 5 * 3 * 2 = 30
Enfoque: la idea es usar hashing para precalcular y almacenar los números de Fibonacci , y luego verificar si un Node contiene un valor de Fibonacci en tiempo O (1).
- Recorra toda la lista enlazada y obtenga el valor máximo en la lista.
- Ahora, para verificar los números de Fibonacci, cree una tabla hash que contenga todos los números de Fibonacci menores o iguales al valor máximo en la lista vinculada.
- Finalmente, recorra los Nodes de la lista enlazada uno por uno y verifique si el Node contiene números de Fibonacci como su valor de datos. Encuentra la suma y el producto de los datos de los Nodes que son Fibonacci.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
Sum = 21 Product = 104
Complejidad de tiempo: O(N) , donde N es el número de Nodes en la lista enlazada.
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA