Sum and Product of the nodes of a Singly Linked List which are divisible by K

0 0 12 minutes read

Given a singly linked list. The task is to find the sum and product of all of the nodes of the given linked list which are divisible by a given number k.

Examples:

Input : List = 7->60->8->40->1
        k = 10 
Output : Product = 2400, Sum = 100
Product of nodes: 60 * 40 = 2400
Input : List = 15->7->3->9->11->5
        k = 5
Output : Product = 75, Sum = 20

Algorithm:

Initialize a pointer ptr with the head of the linked list, a product variable with 1 and a sum variable with 0.

Start traversing the linked list using a loop until all the nodes get traversed.

For every node:

Multiply the value of the current node to the product if current node is divisible by k.

Add the value of the current node to the sum if current node is divisible by k.

Increment the pointer to the next node of linked list i.e. ptr = ptr ->next.

Repeat the above steps until end of linked list is reached.

Finally, print the product and sum.

Below is the implementation of the above approach:

C++

// C++ implementation to find the product
// and sum of nodes which are divisible by k
 
#include <iostream>
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 product and sum of
// nodes which are divisible by k
// of the given linked list
void productAndSum(struct Node* head, int k)
{
    // Pointer to traverse the list
    struct Node* ptr = head;
 
    int product = 1; // Variable to store product
    int sum = 0; // Variable to store sum
 
    // Traverse the list and
    // calculate the product
    // and sum
    while (ptr != NULL) {
        if (ptr->data % k == 0) {
            product *= ptr->data;
            sum += ptr->data;
        }
 
        ptr = ptr->next;
    }
 
    // Print the product and sum
    cout << "Product = " << product << endl;
    cout << "Sum = " << sum;
}
 
// Driver Code
int main()
{
    struct Node* head = NULL;
 
    // create linked list 70->6->8->4->10
    push(&head, 70);
    push(&head, 6);
    push(&head, 8);
    push(&head, 4);
    push(&head, 10);
 
    int k = 10;
 
    productAndSum(head, k);
 
    return 0;
}

Java

// Java implementation to find the product 
// and sum of nodes which are divisible by k 
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 product and sum of 
// nodes which are divisible by k 
// of the given linked list 
static void productAndSum( Node head, int k) 
{ 
    // Pointer to traverse the list 
    Node ptr = head; 
 
    int product = 1; // Variable to store product 
    int sum = 0; // Variable to store sum 
 
    // Traverse the list and 
    // calculate the product 
    // and sum 
    while (ptr != null)
    { 
        if (ptr.data % k == 0)
        { 
            product *= ptr.data; 
            sum += ptr.data; 
        } 
 
        ptr = ptr.next; 
    } 
 
    // Print the product and sum 
    System.out.println( "Product = " + product ); 
    System.out.println( "Sum = " + sum); 
} 
 
// Driver Code 
public static void main(String args[])
{ 
    Node head = null; 
 
    // create linked list 70.6.8.4.10 
    head = push(head, 70); 
    head = push(head, 6); 
    head = push(head, 8); 
    head = push(head, 4); 
    head = push(head, 10); 
 
    int k = 10; 
 
    productAndSum(head, k); 
 
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 implementation to find the product
# and sum of nodes which are divisible by k
import math
 
# 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):
     
    # allocate node 
    new_node =Node(new_data)
 
    # 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 product and sum of
# nodes which are divisible by k
# of the given linked list
def productAndSum(head, k):
     
    # Pointer to traverse the list
    ptr = head
 
    product = 1 # Variable to store product
    add = 0 # Variable to store sum
 
    # Traverse the list and
    # calculate the product
    # and sum
    while (ptr != None):
        if (ptr.data % k == 0):
            product = product * ptr.data
            add = add + ptr.data
     
        ptr = ptr.next
     
    # Print the product and sum
    print("Product =", product)
    print("Sum =", add)
 
# Driver Code
if __name__=='__main__': 
 
    head = None
 
    # create linked list 70.6.8.4.10
    head = push(head, 70)
    head = push(head, 6)
    head = push(head, 8)
    head = push(head, 4)
    head = push(head, 10)
 
    k = 10
 
    productAndSum(head, k)
 
# This code is contributed by Srathore

C#

// C# implementation to find the product 
// and sum of nodes which are divisible by k 
using System;
     
class GFG 
{
     
// A Linked list node 
public 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 product and sum of 
// nodes which are divisible by k 
// of the given linked list 
static void productAndSum( Node head, int k) 
{ 
    // Pointer to traverse the list 
    Node ptr = head; 
 
    int product = 1; // Variable to store product 
    int sum = 0; // Variable to store sum 
 
    // Traverse the list and 
    // calculate the product 
    // and sum 
    while (ptr != null)
    { 
        if (ptr.data % k == 0)
        { 
            product *= ptr.data; 
            sum += ptr.data; 
        } 
 
        ptr = ptr.next; 
    } 
 
    // Print the product and sum 
    Console.WriteLine( "Product = " + product ); 
    Console.WriteLine( "Sum = " + sum); 
} 
 
// Driver Code 
public static void Main(String []args)
{ 
    Node head = null; 
 
    // create linked list 70.6.8.4.10 
    head = push(head, 70); 
    head = push(head, 6); 
    head = push(head, 8); 
    head = push(head, 4); 
    head = push(head, 10); 
 
    int k = 10; 
 
    productAndSum(head, k); 
 
}
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
 
// Javascript implementation to find the product 
// and sum of nodes which are divisible by k     
// A Linked list node
class Node 
{
    constructor(val)
    {
        this.data = val;
        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 product and sum of
// nodes which are divisible by k
// of the given linked list
function productAndSum(head, k) 
{
     
    // Pointer to traverse the list
    var ptr = head;
     
    // Variable to store product
    var product = 1; 
     
    // Variable to store sum
    var sum = 0; 
 
    // Traverse the list and
    // calculate the product
    // and sum
    while (ptr != null) 
    {
        if (ptr.data % k == 0)
        {
            product *= ptr.data;
            sum += ptr.data;
        }
        ptr = ptr.next;
    }
 
    // Print the product and sum
    document.write("Product = " + product);
    document.write("<br/>Sum = " + sum);
}
 
// Driver Code
var head = null;
 
// Create linked list 70.6.8.4.10
head = push(head, 70);
head = push(head, 6);
head = push(head, 8);
head = push(head, 4);
head = push(head, 10);
 
var k = 10;
 
productAndSum(head, k);
 
// This code is contributed by umadevi9616
 
</script>

Output

Product = 700
Sum = 80

Complexity Analysis:

Time Complexity: O(N), where N is the number of nodes in the linked list.
Auxiliary Space: O(1)

Approach : Use a simple iterative traversal of the linked list and performs constant-time operations for each node to compute the product and sum of nodes that are divisible by a given integer k.

Algorithm steps:

Start with an empty linked list, represented by a null head pointer.
Add new nodes to the beginning of the linked list using the push() function. The push() function takes a pointer to the head pointer and the data of the new node as input, creates a new node, sets its data to the input data, sets its next pointer to the current head pointer, and updates the head pointer to point to the new node.
Define a function productAndSum() that takes a pointer to the head of the linked list and an integer k as input.
Initialize two variables product and sum to 1 and 0, respectively.
Traverse the linked list using a pointer ptr. For each node:
a. Check if the node’s data is divisible by k using the modulo operator. If it is, multiply the product variable by the node’s data and add the node’s data to the sum variable.
b. Move the ptr pointer to the next node.
Print the product and sum variables.
Return from the function.

Below is the implementation of the above approach:

C++

//C++ code gfor the above approach
#include <iostream>
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)
{
     
    struct Node* new_node = new Node;
   
    new_node->data = new_data;
 
    new_node->next = (*head_ref);
 
    (*head_ref) = new_node;
}
 
// Recursive function to find the product and sum of
// nodes which are divisible by k of the given linked list
void productAndSumRecursive(struct Node* head, int k, int& product, int& sum)
{
    // Base case: empty list
    if (head == NULL) {
        return;
    }
 
    // Recursive call for the rest of the list
    productAndSumRecursive(head->next, k, product, sum);
 
    // Update product and sum if the current node is divisible by k
    if (head->data % k == 0) {
        product *= head->data;
        sum += head->data;
    }
}
 
// Wrapper function to call the recursive function
void productAndSum(struct Node* head, int k)
{
    int product = 1; 
    int sum = 0; 
 
    // Call the recursive function
    productAndSumRecursive(head, k, product, sum);
 
     
    cout << "Product = " << product << endl;
    cout << "Sum = " << sum;
}
 
// Driver Code
int main()
{
    struct Node* head = NULL;
 
    // create linked list 70->6->8->4->10
    push(&head, 70);
    push(&head, 6);
    push(&head, 8);
    push(&head, 4);
    push(&head, 10);
 
    int k = 10;
 
    productAndSum(head, k);
 
    return 0;
}

Java

// Java implementation to find the product 
// and sum of nodes which are divisible by k
 
class Node {
    int data;
    Node next;
    Node(int val){
        this.data = val;
        this.next = null;
    }
}
 
class GFG {
    static Node head;
    static int product = 1;
    static int sum = 0;
 
    // Function to insert a node at the
    // beginning of the linked list
    static void push(int new_data) {
        // Allocate node 
        Node new_node = new Node(new_data);
        // Link the old list to the new node 
        new_node.next = head;
        // Move the head to point to the new node 
        head = new_node;
    }
 
    // Recursive function to find the product and sum of
    // nodes with are divisible by k of the given linked list
    static void productAndSumRecursive(Node head, int k){
        // Base case: empty list
        if(head == null) return;
 
        // recursive call for the rest of the linked list
        productAndSumRecursive(head.next, k);
        if(head.data % k == 0){
            product = product * head.data;
            sum = sum + head.data;
        }
    }
 
    // Function to find the product and sum of
    // nodes which are divisible by k
    // of the given linked list
    static void productAndSum(Node head, int k) {
        // Call the recursive function
        productAndSumRecursive(head, k);
 
        // Print the product and sum
        System.out.println("Product = " + product);
        System.out.println("Sum = " + sum);
    }
 
    public static void main(String[] args) {
        // Create linked list 70.6.8.4.10
        push(70);
        push(6);
        push(8);
        push(4);
        push(10);
 
        int k = 10;
 
        productAndSum(head, k);
    }
}
// This code is contributed by Chandan Agarwal

Python3

# Python implementation to find the product and sum
# of nodes which are divisible by k in a linked list
 
# A Linked list node
class Node:
    def __init__(self, val):
        self.data = val
        self.next = None
 
# Function to insert a node at the beginning of the linked list
def push(head_ref, new_data):
    # Allocate node
    new_node = Node(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
 
# Recursive function to find the product and sum of
# nodes which are divisible by k in the given linked list
def productAndSumRecursive(head, k):
    global product, sum
    # Base case: empty list
    if head is None:
        return
     
    # Recursive call for the rest of the linked list
    productAndSumRecursive(head.next, k)
    if head.data % k == 0:
        product *= head.data
        sum += head.data
 
# Function to find the product and sum of nodes which are
# divisible by k in the given linked list
def productAndSum(head, k):
    global product, sum
    product = 1
    sum = 0
    # Call the recursive function
    productAndSumRecursive(head, k)
 
    # Print the product and sum
    print("Product =", product)
    print("Sum =", sum)
 
# Driver Code
head = None
 
# Create linked list 70->6->8->4->10
head = push(head, 70)
head = push(head, 6)
head = push(head, 8)
head = push(head, 4)
head = push(head, 10)
 
k = 10
 
productAndSum(head, k)
# THIS CODE IS CONTRIBUTED BY CHANDAN AGARWAL

C#

using System;
 
// A Linked list node
public class Node
{
    public int data;
    public Node next;
}
 
public class GFG
{
    // Function to insert a node at the
    // beginning of the linked list
    public static void Push(ref Node head_ref, int new_data)
    {
        Node new_node = new Node();
 
        new_node.data = new_data;
        new_node.next = head_ref;
 
        head_ref = new_node;
    }
 
    // Recursive function to find the product and sum of
    // nodes which are divisible by k of the given linked list
    public static void ProductAndSumRecursive(Node head, int k, ref int product, ref int sum)
    {
        // Base case: empty list
        if (head == null)
        {
            return;
        }
 
        // Recursive call for the rest of the list
        ProductAndSumRecursive(head.next, k, ref product, ref sum);
 
        // Update product and sum if the current node is divisible by k
        if (head.data % k == 0)
        {
            product *= head.data;
            sum += head.data;
        }
    }
 
    // Wrapper function to call the recursive function
    public static void ProductAndSum(Node head, int k)
    {
        int product = 1;
        int sum = 0;
 
        // Call the recursive function
        ProductAndSumRecursive(head, k, ref product, ref sum);
 
        Console.WriteLine("Product = " + product);
        Console.WriteLine("Sum = " + sum);
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        Node head = null;
 
        // create linked list 70->6->8->4->10
        Push(ref head, 70);
        Push(ref head, 6);
        Push(ref head, 8);
        Push(ref head, 4);
        Push(ref head, 10);
 
        int k = 10;
 
        ProductAndSum(head, k);
    }
}
 
// This code is contributed by rambabuguphka

Javascript

// Javascript implementation to find the product 
// and sum of nodes which are divisible by k     
// A Linked list node
class Node {
    constructor(val){
        this.data = val;
        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;
}
 
// Recursive function to find the product and sum of
// nodes with are divisible by k of the given linked list
function productAndSumRecursive(head, k){
    // Base case: empty list
    if(head == null) return;
     
    // recursive call for the rest of the linked list
    productAndSumRecursive(head.next, k);
    if(head.data % k == 0){
        product = product * head.data;
        sum = sum + head.data;
    }
}
 
// Function to find the product and sum of
// nodes which are divisible by k
// of the given linked list
var product = 1;
var sum = 0;
function productAndSum(head, k) {
    // Call the recursive function
    productAndSumRecursive(head, k, product, sum);
 
    // Print the product and sum
    console.log("Product = " + product);
    console.log("Sum = " + sum);
}
 
// Driver Code
var head = null;
 
// Create linked list 70.6.8.4.10
head = push(head, 70);
head = push(head, 6);
head = push(head, 8);
head = push(head, 4);
head = push(head, 10);
 
var k = 10;
 
productAndSum(head, k);
// THIS CODE IS CONTRIBUTED BY CHANDAN AGARWAL

Output

Product = 700
Sum = 80

Time Complexity: O(n), where n is the number of nodes in the linked list.
Auxiliary Space: O(1), because we only use a fixed amount of additional memory that does not depend on the size of the input.

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!