Dada una lista enlazada, la tarea es encontrar la suma de todos los subconjuntos de una lista enlazada.
Ejemplos:
Entrada: 2 -> 3 -> NULL
Salida: 10
Explicación:
Todos los subconjuntos no vacíos son {2}, {3} y {2, 3}
Suma total = 2 + 3 + (2 + 3) = 10
Entrada: 2 -> 1 -> 5 -> 6 -> NULO
Salida: 112
Enfoque: Considerando todos los subconjuntos posibles, podemos observar que cada Node aparece 2 (N – 1) veces. Así, el producto de la suma de todos los Nodes y 2 (N – 1) nos da la respuesta final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// sum of values of all subsets of linked list.
#include <bits/stdc++.h>
using namespace std;
/* A Linked list node */
struct Node {
int data;
struct Node* next;
};
// function to insert a node at the
// beginning of the linked list
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = new Node;
/* put in 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 to the new node */
(*head_ref) = new_node;
}
// function to find the
// sum of values of all subsets of linked list.
int sumOfNodes(struct Node* head)
{
struct Node* ptr = head;
int sum = 0;
int n = 0; // size of linked list
while (ptr != NULL) {
sum += ptr->data;
ptr = ptr->next;
n++;
}
// Every element appears 2^(n-1) times
sum = sum * pow(2, n - 1);
return sum;
}
// Driver program to test above
int main()
{
struct Node* head = NULL;
// create linked list 2->1->5->6
push(&head, 2);
push(&head, 1);
push(&head, 5);
push(&head, 6);
cout << sumOfNodes(head);
return 0;
}
Java
// Java implementation to find the
// sum of values of all subsets of linked list.
import java.util.*;
class GFG{
/* A Linked list node */
static class Node {
int data;
Node next;
};
// function to insert a node at the
// beginning of the linked list
static Node push(Node head_ref, int new_data)
{
/* allocate node */
Node new_node = new Node();
/* put in 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 to the new node */
head_ref = new_node;
return head_ref;
}
// function to find the
// sum of values of all subsets of linked list.
static int sumOfNodes(Node head)
{
Node ptr = head;
int sum = 0;
int n = 0; // size of linked list
while (ptr != null) {
sum += ptr.data;
ptr = ptr.next;
n++;
}
// Every element appears 2^(n-1) times
sum = (int) (sum * Math.pow(2, n - 1));
return sum;
}
// Driver program to test above
public static void main(String[] args)
{
Node head = null;
// create linked list 2.1.5.6
head = push(head, 2);
head = push(head, 1);
head = push(head, 5);
head = push(head, 6);
System.out.print(sumOfNodes(head));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation to find the # sum of values of all subsets of linked list. # A Linked list node class Node: def __init__(self,data): self.data = data self.next = None # function to insert a node at the # beginning of the linked list def push(head_ref,new_data): new_node=Node(new_data) #new_node.data = new_data new_node.next = head_ref head_ref = new_node return head_ref # function to find the # sum of values of all subsets of linked list. def sumOfNodes(head): ptr = head sum = 0 n = 0 # size of linked list while (ptr != None) : sum += ptr.data ptr = ptr.next n += 1 # Every element appears 2^(n-1) times sum = sum * pow(2, n - 1) return sum # Driver program to test above if __name__=='__main__': head = None # create linked list 2.1.5.6 head = push(head, 2) head = push(head, 1) head = push(head, 5) head = push(head, 6) print(sumOfNodes(head)) # This code is contributed by AbhiThakur
C#
// C# implementation to find the
// sum of values of all subsets of linked list.
using System;
class GFG{
/* A Linked list node */
class Node {
public int data;
public Node next;
};
// function to insert a node at the
// beginning of the linked list
static Node push(Node head_ref, int new_data)
{
/* allocate node */
Node new_node = new Node();
/* put in 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 to the new node */
head_ref = new_node;
return head_ref;
}
// function to find the
// sum of values of all subsets of linked list.
static int sumOfNodes(Node head)
{
Node ptr = head;
int sum = 0;
int n = 0; // size of linked list
while (ptr != null) {
sum += ptr.data;
ptr = ptr.next;
n++;
}
// Every element appears 2^(n-1) times
sum = (int) (sum * Math.Pow(2, n - 1));
return sum;
}
// Driver program to test above
public static void Main(String[] args)
{
Node head = null;
// create linked list 2.1.5.6
head = push(head, 2);
head = push(head, 1);
head = push(head, 5);
head = push(head, 6);
Console.Write(sumOfNodes(head));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation to find the
// sum of values of all subsets of linked list.
/* A Linked list node */
class Node {
constructor()
{
this.data = 0;
this.next = null;
}
};
// function to insert a node at the
// beginning of the linked list
function push(head_ref, new_data)
{
/* allocate node */
var new_node = new Node;
/* put in 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 to the new node */
(head_ref) = new_node;
return head_ref;
}
// function to find the
// sum of values of all subsets of linked list.
function sumOfNodes(head)
{
var ptr = head;
var sum = 0;
var n = 0; // size of linked list
while (ptr != null) {
sum += ptr.data;
ptr = ptr.next;
n++;
}
// Every element appears 2^(n-1) times
sum = sum * Math.pow(2, n - 1);
return sum;
}
// Driver program to test above
var head = null;
// create linked list 2.1.5.6
head = push(head, 2);
head = push(head, 1);
head = push(head, 5);
head = push(head, 6);
document.write( sumOfNodes(head));
// This code is contributed by noob2000.
</script>
Producción:
112
Complejidad de tiempo: O(N)