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 nodestruct 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 product and sum of// nodes which are divisible by k// of the given linked listvoid 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 Codeint 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 kimport math# A Linked list nodeclass 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): # 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 listdef 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 Codeif __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 nodeclass Node { constructor(val) { this.data = val; 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 product and sum of// nodes which are divisible by k// of the given linked listfunction 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 Codevar head = null;// Create linked list 70.6.8.4.10head = 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 nodestruct 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){ 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 listvoid 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 functionvoid 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 Codeint 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 kclass 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 nodeclass Node: def __init__(self, val): self.data = val self.next = None# Function to insert a node at the beginning of the linked listdef 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 listdef 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 listdef 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 Codehead = None# Create linked list 70->6->8->4->10head = push(head, 70)head = push(head, 6)head = push(head, 8)head = push(head, 4)head = push(head, 10)k = 10productAndSum(head, k)# THIS CODE IS CONTRIBUTED BY CHANDAN AGARWAL |
C#
using System;// A Linked list nodepublic 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 nodeclass Node { constructor(val){ this.data = val; 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;}// Recursive function to find the product and sum of// nodes with are divisible by k of the given linked listfunction 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 listvar 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 Codevar head = null;// Create linked list 70.6.8.4.10head = 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
