Given a Linked List and a key K. The task is to calculate the sum and product all the nodes from the list that are lesser than the key K.
Examples:
Input: 12 -> 15 -> 9 -> 11 -> 5 -> 6, K = 9
Output: Sum = 11, Product = 30Input: 13 -> 4 -> 16 -> 9 -> 22 -> 45 -> 5 -> 16 -> 6, K = 10
Output: Sum = 24, Product = 1080
Approach: Start traversing from the head and check if current node’s value is less than K. If yes, then add that node to the sum and multiply that node for the product and move forward in the list.
Below is the implementation of the above approach:
C++
// C++ program to sum and product all the// nodes from the list that are lesser// than the specified value K#include <bits/stdc++.h>using namespace std;// structure of a nodestruct Node { int data; Node* next;};// function to get a new nodeNode* getNode(int data){ Node* newNode = new Node; newNode->data = data; newNode->next = NULL; return newNode;}// function to sum all the nodes from the list// that are lesser than the specified value Kint sumLesserNodes(Node** head_ref, int K){ Node* temp = *head_ref; int sum = 0; while (temp != NULL) { if (temp->data < K) sum += temp->data; temp = temp->next; } return sum;}// function to product all the nodes from the list// that are lesser than the specified value Kint productLesserNodes(Node** head_ref, int K){ Node* temp = *head_ref; int product = 1; while (temp != NULL) { if (temp->data < K) product *= temp->data; temp = temp->next; } return product;}// Driver codeint main(){ // Create list: 12->15->9->11->5->6 Node* head = getNode(12); head->next = getNode(15); head->next->next = getNode(9); head->next->next->next = getNode(11); head->next->next->next->next = getNode(5); head->next->next->next->next->next = getNode(6); int K = 9; cout << "Sum = " << sumLesserNodes(&head, K) << endl; cout << "Product = " << productLesserNodes(&head, K) << endl; return 0;} |
Java
// Java program to sum and product all the// nodes from the list that are lesser// than the specified value Kclass GFG {// structure of a nodestatic class Node { int data; Node next;};// function to get a new nodestatic Node getNode(int data){ Node newNode = new Node(); newNode.data = data; newNode.next = null; return newNode;}// function to sum all the nodes from the list// that are lesser than the specified value Kstatic int sumLesserNodes(Node head_ref, int K){ Node temp = head_ref; int sum = 0; while (temp != null) { if (temp.data < K) sum += temp.data; temp = temp.next; } return sum;}// function to product all the nodes from the list// that are lesser than the specified value Kstatic int productLesserNodes(Node head_ref, int K){ Node temp = head_ref; int product = 1; while (temp != null) { if (temp.data < K) product *= temp.data; temp = temp.next; } return product;}// Driver codepublic static void main(String[] args) { // Create list: 12->15->9->11->5->6 Node head = getNode(12); head.next = getNode(15); head.next.next = getNode(9); head.next.next.next = getNode(11); head.next.next.next.next = getNode(5); head.next.next.next.next.next = getNode(6); int K = 9; System.out.println("Sum = " + sumLesserNodes(head, K)); System.out.println("Product = " + productLesserNodes(head, K));}}// This code has been contributed by 29AjayKumar |
Python3
# Python3 program to sum and product all the# nodes from the list that are lesser# than the specified value K# Node of the single linked list class Node: def __init__(self, data): self.data = data self.next = None# function to get a new nodedef getNode(data): newNode = Node(0) newNode.data = data newNode.next = None return newNode# function to sum all the nodes from the list# that are lesser than the specified value Kdef sumLesserNodes(head_ref, K): temp = head_ref sum = 0 while (temp != None) : if (temp.data < K): sum += temp.data temp = temp.next return sum# function to product all the nodes from the list# that are lesser than the specified value Kdef productLesserNodes(head_ref,K): temp = head_ref product = 1 while (temp != None) : if (temp.data < K): product *= temp.data temp = temp.next return product# Driver Codeif __name__ == "__main__": # Create list: 12.15.9.11.5.6 head = getNode(12) head.next = getNode(15) head.next.next = getNode(9) head.next.next.next = getNode(11) head.next.next.next.next = getNode(5) head.next.next.next.next.next = getNode(6) K = 9 print("Sum =", sumLesserNodes(head, K)) print("Product =", productLesserNodes(head, K))# This code is contributed by Arnab Kundu |
C#
// C# program to sum and product all the// nodes from the list that are lesser// than the specified value Kusing System; class GFG {// structure of a nodepublic class Node { public int data; public Node next;};// function to get a new nodestatic Node getNode(int data){ Node newNode = new Node(); newNode.data = data; newNode.next = null; return newNode;}// function to sum all the nodes from the list// that are lesser than the specified value Kstatic int sumLesserNodes(Node head_ref, int K){ Node temp = head_ref; int sum = 0; while (temp != null) { if (temp.data < K) sum += temp.data; temp = temp.next; } return sum;}// function to product all the nodes from the list// that are lesser than the specified value Kstatic int productLesserNodes(Node head_ref, int K){ Node temp = head_ref; int product = 1; while (temp != null) { if (temp.data < K) product *= temp.data; temp = temp.next; } return product;}// Driver codepublic static void Main(String[] args) { // Create list: 12->15->9->11->5->6 Node head = getNode(12); head.next = getNode(15); head.next.next = getNode(9); head.next.next.next = getNode(11); head.next.next.next.next = getNode(5); head.next.next.next.next.next = getNode(6); int K = 9; Console.WriteLine("Sum = " + sumLesserNodes(head, K)); Console.WriteLine("Product = " + productLesserNodes(head, K));}}// This code contributed by Rajput-Ji |
Javascript
<script>// JavaScript program to sum and product all the// nodes from the list that are lesser// than the specified value Kclass Node { constructor() { this.data=0; this.next=null; }}// function to get a new nodefunction getNode(data){ let newNode = new Node(); newNode.data = data; newNode.next = null; return newNode;}// function to sum all the nodes from the list// that are lesser than the specified value Kfunction sumLesserNodes(head_ref,K){ let temp = head_ref; let sum = 0; while (temp != null) { if (temp.data < K) sum += temp.data; temp = temp.next; } return sum;}// function to product all the nodes from the list// that are lesser than the specified value Kfunction productLesserNodes(head_ref,K){ let temp = head_ref; let product = 1; while (temp != null) { if (temp.data < K) product *= temp.data; temp = temp.next; } return product;}// Driver code// Create list: 12->15->9->11->5->6let head = getNode(12);head.next = getNode(15);head.next.next = getNode(9);head.next.next.next = getNode(11);head.next.next.next.next = getNode(5);head.next.next.next.next.next = getNode(6);let K = 9;document.write("Sum = " + sumLesserNodes(head, K)+"<br>");document.write("Product = " + productLesserNodes(head, K)+"<br>");// This code is contributed by avanitrachhadiya2155</script> |
Output
Sum = 11 Product = 30
Complexity Analysis:
- Time Complexity: O(N).
- Auxiliary Space: O(1) because it is using constant space.
Recursive Approach:
This approach uses a recursive function to calculate the sum and product of nodes that are lesser than the given key K.
- We start by checking if the current node is NULL.
- If it is, we return. Otherwise, we check if the data of the current node is lesser than K.
- If it is, we add it to the sum and multiply it to the product.
- Then, we call the recursive function with the next node as the head.
- This function call traverses the linked list recursively until the end and calculates the sum and product of nodes that are lesser than K.
- Finally, we return the sum and product.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std; // Linked List nodestruct Node { int data; Node* next;}; // Function to create a new nodeNode* getNode(int data) { Node* newNode = new Node; newNode->data = data; newNode->next = NULL; return newNode;} // Recursive function to calculate the sum and product of nodes lesser than Kvoid sumProductLesserNodes(Node* head, int K, int& sum, int& product) { if (head == NULL) { return; } if (head->data < K) { sum += head->data; product *= head->data; } sumProductLesserNodes(head->next, K, sum, product);} // Driver codeint main() { // Create list: 12->15->9->11->5->6 Node* head = getNode(12); head->next = getNode(15); head->next->next = getNode(9); head->next->next->next = getNode(11); head->next->next->next->next = getNode(5); head->next->next->next->next->next = getNode(6); int K = 9; int sum = 0, product = 1; sumProductLesserNodes(head, K, sum, product); cout << "Sum = " << sum << endl; cout << "Product = " << product << endl; return 0;} |
Java
class GFG { int data; GFG next; // Constructor to create a new node public GFG(int data) { this.data = data; this.next = null; }}public class Main { // Recursive function to calculate the // sum and product of nodes lesser than K public static void sumProductLesserNodes(GFG head, int K, int[] result) { if (head == null) { return; } if (head.data < K) { result[0] += head.data;// Sum result[1] *= head.data;// Product } sumProductLesserNodes(head.next, K, result); } // Driver code public static void main(String[] args) { // Create list: 12->15->9->11->5->6 GFG head = new GFG(12); head.next = new GFG(15); head.next.next = new GFG(9); head.next.next.next = new GFG(11); head.next.next.next.next = new GFG(5); head.next.next.next.next.next = new GFG(6); int K = 9; int[] result = {0, 1}; sumProductLesserNodes(head, K, result); System.out.println("Sum = " + result[0]); System.out.println("Product = " + result[1]); }} |
Python3
# Linked List nodeclass Node: def __init__(self, data): self.data = data self.next = None# Recursive function to calculate the sum and product of nodes lesser than Kdef sum_product_lesser_nodes(head, K, sum, product): if head is None: return sum, product # Return the sum and product when the list is empty # If the data in the current node is less than K, update the sum and product if head.data < K: sum += head.data product *= head.data # Recursively call the function for the next node in the linked list return sum_product_lesser_nodes(head.next, K, sum, product)# Driver codeif __name__ == "__main__": # Create list: 12->15->9->11->5->6 head = Node(12) head.next = Node(15) head.next.next = Node(9) head.next.next.next = Node(11) head.next.next.next.next = Node(5) head.next.next.next.next.next = Node(6) K = 9 sum = 0 product = 1 sum, product = sum_product_lesser_nodes(head, K, sum, product) print("Sum =", sum) print("Product =", product)# This code is contributed by shivamgupta310570 |
C#
using System;public class Node { public int data; public Node next;}public class GFG { // Function to create a new node public static Node GetNode(int data) { Node newNode = new Node(); newNode.data = data; newNode.next = null; return newNode; } // Recursive function to calculate the sum and product // of nodes lesser than K public static void SumProductLesserNodes(Node head, int K, ref int sum, ref int product) { if (head == null) { return; } if (head.data < K) { sum += head.data; product *= head.data; } SumProductLesserNodes(head.next, K, ref sum, ref product); } // Driver code public static void Main() { // Create list: 12->15->9->11->5->6 Node head = GetNode(12); head.next = GetNode(15); head.next.next = GetNode(9); head.next.next.next = GetNode(11); head.next.next.next.next = GetNode(5); head.next.next.next.next.next = GetNode(6); int K = 9; int sum = 0, product = 1; SumProductLesserNodes(head, K, ref sum, ref product); Console.WriteLine("Sum = " + sum); Console.WriteLine("Product = " + product); }} |
Javascript
// Linked List nodeclass Node {constructor(data) {this.data = data;this.next = null;}}// Function to create a new nodefunction getNode(data) {const newNode = new Node(data);return newNode;}// Recursive function to calculate the sum and product of nodes lesser than Kfunction sumProductLesserNodes(head, K, sum, product) {if (!head) {return;}if (head.data < K) {sum[0] += head.data;product[0] *= head.data;}sumProductLesserNodes(head.next, K, sum, product);}// Driver code// Create list: 12->15->9->11->5->6const head = getNode(12);head.next = getNode(15);head.next.next = getNode(9);head.next.next.next = getNode(11);head.next.next.next.next = getNode(5);head.next.next.next.next.next = getNode(6);const K = 9;const sum = [0], product = [1];sumProductLesserNodes(head, K, sum, product);console.log(`Sum = ${sum[0]}`);console.log(`Product = ${product[0]}`); |
Output
Sum = 11 Product = 30
Time Complexity: O(n), where n is the number of nodes in the linked list.
Auxiliary Space: O(n), This is because each function call creates a new stack frame with the function arguments and local variables. Since we are making n function calls in the worst case (when all nodes are lesser than K), the maximum stack space used will be O(n).
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!
