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)