Sum of all subset sums of a linked list
Given a linked list, the task is to find the sum of all subsets of a linked list.
Examples:
Input: 2 -> 3 -> NULL
Output: 10
Explanation:
All non-empty subsets are {2}, {3} and {2, 3}
Total sum = 2 + 3 + (2 + 3) = 10
Input: 2 -> 1 -> 5 -> 6 -> NULL
Output: 112
Approach: Considering all the possible subsets, we can observe that each node appears 2(N – 1) times. Thus, the product of sum of all nodes and 2(N – 1) gives us the final answer.
Below is the implementation of the above approach:
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> |
Output:
112
Time Complexity: O(N)
The time complexity of this algorithm is O(N) as we need to traverse the linked list with n nodes to calculate the sum.
Space Complexity: O(1).
No extra space is required to store any values as all values are calculated on the go.