Sum and Product of all the nodes which are less than K in the linked list

0 0 9 minutes read

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 = 30

Input: 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 node
struct Node {
    int data;
    Node* next;
};
 
// function to get a new node
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 K
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 K
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 code
int 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 K
class GFG 
{
 
// structure of a node
static class Node 
{
    int data;
    Node next;
};
 
// function to get a new node
static 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 K
static 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 K
static 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 code
public 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 node
def 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 K
def 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 K
def 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 Code
if __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 K
using System;
     
class GFG 
{
 
// structure of a node
public class Node 
{
    public int data;
    public Node next;
};
 
// function to get a new node
static 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 K
static 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 K
static 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 code
public 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 K
 
class Node 
{
    constructor()
    {
        this.data=0;
        this.next=null;
    }
}
 
// function to get a new node
function 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 K
function 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 K
function 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->6
let 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 node
struct Node {
    int data;
    Node* next;
};
  
// Function to create a new node
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
void 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 code
int 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 node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
# Recursive function to calculate the sum and product of nodes lesser than K
 
 
def 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 code
if __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 node
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
 
// Function to create a new node
function getNode(data) {
const newNode = new Node(data);
return newNode;
}
 
// Recursive function to calculate the sum and product of nodes lesser than K
function 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->6
const 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 zambiatek!