Given a singly circular linked list. The task is to find the sum and product of nodes that are divisible by K of the given linked list.
Examples:
Input : List = 5->6->7->8->9->10->11->11
K = 11
Output : Sum = 22, Product = 121
Input : List = 15->7->3->9->11->5
K = 5
Output : Product = 75, Sum = 20
Sum And Product of Singly Circular Linked List Node
Approach:
- Initialize a pointer current with the head of the circular linked list and a sum variable sum with 0 and a product variable product with 1.
- Start traversing the linked list using a do-while loop until all the nodes get traversed.
- If current node data is divisible by the given key.
- Add the value of current node to the sum i.e. sum = sum + current -> data.
- Multiply the value of the current node to the product i.e. product = product * current -> data.
- Increment the pointer to the next node of the linked list i.e. temp = temp -> next.
- Print the sum and product.
Below is the implementation of the above approach:
C++
// C++ program to calculate sum and product from// singly circular linked list nodes// which are divisible by given key#include <bits/stdc++.h>using namespace std;// Circular list nodestruct Node { int data; struct Node* next;};// Function to calculate sum and productvoid sumProduct(struct Node* head, int key){ struct Node* current = head; int sum = 0, product = 1; // if list is empty simply show message if (head == NULL) { printf("\nDisplay List is empty\n"); return; } // traverse first to last node else { do { // check if current node's data is // divisible by key if ((current->data) % key == 0) { // Calculate sum sum += current->data; // Calculate product product *= current->data; } current = current->next; } while (current != head); } cout << "Sum = " << sum << ", Product = " << product;}// Function print the listvoid displayList(struct Node* head){ struct Node* current = head; // if list is empty simply show message if (head == NULL) { printf("\nDisplay List is empty\n"); return; } // traverse first to last node else { do { printf("%d ", current->data); current = current->next; } while (current != head); }}// Function to insert a node at the end of// a Circular linked listvoid InsertNode(struct Node** head, int data){ struct Node* current = *head; // Create a new node struct Node* newNode = new Node; // check node is created or not if (!newNode) { printf("\nMemory Error\n"); return; } // insert data into newly created node newNode->data = data; // check list is empty // if not have any node then // make first node it if (*head == NULL) { newNode->next = newNode; *head = newNode; return; } // if list have already some node else { // move first node to last node while (current->next != *head) { current = current->next; } // put first or head node address in new node link newNode->next = *head; // put new node address into last node link(next) current->next = newNode; }}// Driver Codeint main(){ struct Node* head = NULL; InsertNode(&head, 5); InsertNode(&head, 6); InsertNode(&head, 7); InsertNode(&head, 8); InsertNode(&head, 9); InsertNode(&head, 10); InsertNode(&head, 11); InsertNode(&head, 11); cout << "Initial List: "; displayList(head); cout << endl; sumProduct(head, 11); return 0;} |
Java
// Java program to calculate sum and product from // singly circular linked list nodes // which are divisible by given key import java.util.*;class Solution{ // Circular list node static class Node { int data; Node next; } // Function to calculate sum and product static void sumProduct( Node head, int key) { Node current = head; int sum = 0, product = 1; // if list is empty simply show message if (head == null) { System.out.print("\nDisplay List is empty\n"); return; } // traverse first to last node else { do { // check if current node's data is // divisible by key if ((current.data) % key == 0) { // Calculate sum sum += current.data; // Calculate product product *= current.data; } current = current.next; } while (current != head); } System.out.print( "Sum = " + sum + ", Product = " + product); } // Function print the list static void displayList( Node head) { Node current = head; // if list is empty simply show message if (head == null) { System.out.print("\nDisplay List is empty\n"); return; } // traverse first to last node else { do { System.out.print( current.data+" "); current = current.next; } while (current != head); } } // Function to insert a node at the end of // a Circular linked list static Node InsertNode( Node head, int data) { Node current = head; // Create a new node Node newNode = new Node(); // check node is created or not if (newNode==null) { System.out.print("\nMemory Error\n"); return head; } // insert data into newly created node newNode.data = data; // check list is empty // if not have any node then // make first node it if (head == null) { newNode.next = newNode; head = newNode; return head; } // if list have already some node else { // move first node to last node while (current.next != head) { current = current.next; } // put first or head node address in new node link newNode.next = head; // put new node address into last node link(next) current.next = newNode; } return head;} // Driver Code public static void main(String args[]){ Node head=null ; head =InsertNode(head, 5); head =InsertNode(head, 6); head =InsertNode(head, 7); head =InsertNode(head, 8); head =InsertNode(head, 9); head =InsertNode(head, 10); head =InsertNode(head, 11); head =InsertNode(head, 11); System.out.print( "Initial List: "); displayList(head); System.out.println(); sumProduct(head, 11); }}//contributed by Arnab Kundu |
Python3
# Python3 program to calculate sum and # product from singly circular linked list # nodes which are divisible by given keyimport math # Circular list nodeclass Node: def __init__(self, data): self.data = data self.next = None# Function to calculate sum and productdef sumProduct(head, key): current = head sum = 0 product = 1 # if list is empty simply show message if (head == None): print("\nDisplay List is empty\n") return # traverse first to last node else : # check if current node's data is # divisible by key if ((current.data) % key == 0) : # Calculate sum sum = sum + current.data # Calculate product product = product * current.data current = current.next while (current != head): if ((current.data) % key == 0) : # Calculate sum sum = sum + current.data # Calculate product product = product * current.data current = current.next print("\nSum =", sum, end = ", ") print("Product =", product)# Function print the listdef displayList(head): current = head # if list is empty simply show message if (head == None): print("\nDisplay List is empty\n") return # traverse first to last node else : print(current.data, end = " ") current = current.next while (current != head): print(current.data, end = " ") current = current.next # Function to insert a node at the end of# a Circular linked listdef InsertNode(head, data): current = head # Create a new node newNode = Node(data) # check node is created or not if (newNode == None): print("\nMemory Error\n") return head # insert data o newly created node newNode.data = data # check list is empty # if not have any node then # make first node it if (head == None): newNode.next = newNode head = newNode return head # if list have already some node else : # move first node to last node while (current.next != head): current = current.next # put first or head node address # in new node link newNode.next = head # put new node address o last node link(next) current.next = newNode return head# Driver Codeif __name__=='__main__': head = None head = InsertNode(head, 5) head = InsertNode(head, 6) head = InsertNode(head, 7) head = InsertNode(head, 8) head = InsertNode(head, 9) head = InsertNode(head, 10) head = InsertNode(head, 11) head = InsertNode(head, 11) print("Initial List: ", end = "") displayList(head) sumProduct(head, 11)# This code is contributed by Srathore |
C#
// C# program to calculate sum and product from // singly circular linked list nodes // which are divisible by given key using System; class GFG{ // Circular list node class Node { public int data; public Node next; } // Function to calculate sum and product static void sumProduct( Node head, int key) { Node current = head; int sum = 0, product = 1; // if list is empty simply show message if (head == null) { Console.Write("\nDisplay List is empty\n"); return; } // traverse first to last node else { do { // check if current node's data is // divisible by key if ((current.data) % key == 0) { // Calculate sum sum += current.data; // Calculate product product = current.data; } current = current.next; } while (current != head); } Console.Write( "Sum = " + sum + ", Product = " + product); } // Function print the list static void displayList( Node head) { Node current = head; // if list is empty simply show message if (head == null) { Console.Write("\nDisplay List is empty\n"); return; } // traverse first to last node else { do { Console.Write( current.data+" "); current = current.next; } while (current != head); } } // Function to insert a node at the end of // a Circular linked list static Node InsertNode( Node head, int data) { Node current = head; // Create a new node Node newNode = new Node(); // check node is created or not if (newNode==null) { Console.Write("\nMemory Error\n"); return head; } // insert data into newly created node newNode.data = data; // check list is empty // if not have any node then // make first node it if (head == null) { newNode.next = newNode; head = newNode; return head; } // if list have already some node else { // move first node to last node while (current.next != head) { current = current.next; } // put first or head node address in new node link newNode.next = head; // put new node address into last node link(next) current.next = newNode; } return head; } // Driver Code public static void Main() { Node head=null ; head =InsertNode(head, 5); head =InsertNode(head, 6); head =InsertNode(head, 7); head =InsertNode(head, 8); head =InsertNode(head, 9); head =InsertNode(head, 10); head =InsertNode(head, 11); head =InsertNode(head, 11); Console.Write( "Initial List: "); displayList(head); Console.WriteLine(); sumProduct(head, 11); }}// This code has been contributed // by PrinciRaj1992 |
Javascript
<script>// JavaScript program to calculate// sum and product from // singly circular linked list nodes // which are divisible by given key // Circular list nodeclass Node { constructor() { this.data = 0; this.next = null; }} // Function to calculate sum and product function sumProduct(head , key) { var current = head; var sum = 0, product = 1; // if list is empty simply show message if (head == null) { document.write("\nDisplay List is empty\n"); return; } // traverse first to last node else { do { // check if current node's data is // divisible by key if ((current.data) % key == 0) { // Calculate sum sum += current.data; // Calculate product product *= current.data; } current = current.next; } while (current != head); } document.write("Sum = " + sum + ", Product = " + product); } // Function print the list function displayList(head) { var current = head; // if list is empty simply show message if (head == null) { document.write("\nDisplay List is empty\n"); return; } // traverse first to last node else { do { document.write(current.data + " "); current = current.next; } while (current != head); } } // Function to insert a node at the end of // a Circular linked list function InsertNode(head , data) { var current = head; // Create a new node var newNode = new Node(); // check node is created or not if (newNode == null) { document.write("\nMemory Error\n"); return head; } // insert data into newly created node newNode.data = data; // check list is empty // if not have any node then // make first node it if (head == null) { newNode.next = newNode; head = newNode; return head; } // if list have already some node else { // move first node to last node while (current.next != head) { current = current.next; } // put first or head node // address in new node link newNode.next = head; // put new node address into // last node link(next) current.next = newNode; } return head; } // Driver Code var head = null; head = InsertNode(head, 5); head = InsertNode(head, 6); head = InsertNode(head, 7); head = InsertNode(head, 8); head = InsertNode(head, 9); head = InsertNode(head, 10); head = InsertNode(head, 11); head = InsertNode(head, 11); document.write("Initial List: "); displayList(head); document.write("<br/>"); sumProduct(head, 11);// This code is contributed by todaysgaurav</script> |
Output
Initial List: 5 6 7 8 9 10 11 11 Sum = 22, Product = 121
Complexity Analysis:
- Time Complexity: O(n), as we are using a loop to traverse n times. Where n is the number of nodes in the linked list.
- Auxiliary Space: O(1), as we are not using any extra space.
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!
… [Trackback]
[…] Read More to that Topic: geeksforgeeks.org/sum-and-product-of-the-nodes-of-a-circular-singly-linked-list-which-are-divisible-by-k/ […]