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 listvoid 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 aboveint 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 liststatic 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 abovepublic 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 listdef 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 aboveif __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 liststatic 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 abovepublic 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 listfunction 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 abovevar head = null;// create linked list 2.1.5.6head = 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.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
