Sum and Product of the nodes of a Singly Linked List which are divisible by K
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.
Contact Us