Given a circular singly linked list containing N nodes, The task is to find the sum and product of all the nodes from the list whose data value has an even digit sum.
Examples:
Input: List = 15 -> 16 -> 8 -> 6 -> 13
Output: Sum = 42, Product = 9360
Explanation:
The circular linked list contains:
15 -> 1 + 5 = 6
16 -> 1 + 6 = 7
8 -> 8
6 -> 6
13 -> 1 + 3 = 4
The list contains 4 Even Digit Sum data values 15, 8, 6 and 13.
Sum = 15 + 8 + 6 + 13 = 42
Product = 15 * 8 * 6 * 13 = 9360Input: List = 5 -> 3 -> 4 -> 2 -> 9
Output: Sum = 6, Product = 8
Explanation:
The list contains 2 Even Digit Sum data values 4 and 2.
Sum = 4 + 2 = 6
Product = 4 * 2 = 8
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 value has an even digit sum.
- Add the value of current node to the sum i.e. sum = sum + current -> data.
- Multiply the value of current node to the product i.e. product = product * current -> data.
- Increment the pointer to the next node of linked list i.e. temp = temp -> next.
- Print the sum and product.
Below is the implementation of the above approach:
C++
// C++ implementation to find the sum and// product of all of the Even Digit sum nodes// in a circularly linked list#include <bits/stdc++.h>using namespace std;// Circular list nodestruct Node { int data; struct Node* next;};// Function to find the digit sum// for a numberint digitSum(int num){ int sum = 0; while (num) { sum += (num % 10); num /= 10; } return sum;}// 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("\nList is empty\n"); return; } // Traverse first to last node else { do { // Check if current node's // data has an even digit sum if (!(digitSum(current->data) & 1)) { // 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("\nList 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, 13); InsertNode(&head, 6); InsertNode(&head, 8); InsertNode(&head, 15); InsertNode(&head, 16); cout << "Initial List: "; DisplayList(head); cout << endl; SumProduct(head, 11); return 0;} |
Java
// Java implementation to find the sum and // product of all of the Even Digit sum nodes // in a circularly linked list class GFG{// Structure for a nodestatic class Node{ int data; Node next;}// Function to calculate the sum of// individual digitsstatic int digitSum(int n){ int sum = 0; while (n != 0) { sum += n % 10; n /= 10; } return sum;}// Function to calculate sum and// productstatic void SumProduct(Node head){ Node temp = head; int Sum = 0; int Prod = 1; do { // Check if current node's // data has an even digit sum if (digitSum(temp.data) % 2 == 0) { Sum += temp.data; Prod *= temp.data; } temp = temp.next; } while (temp != head); System.out.print("Sum = " + Sum); System.out.print(", Product = " + Prod);}// Function print the liststatic void DisplayList(Node head){ Node temp = head; if (head != null) { do { // Traverse first to last node System.out.print(temp.data + " "); temp = temp.next; } while (temp != head); } System.out.println();}// Function to insert a node at the ending// of a Circular linked liststatic Node InsertNode(int key, Node head){ // Create a new node Node new_node = new Node(); new_node.data = key; // If linked list is null then // make the first node as head // after insertion if (head == null) { head = new_node; new_node.next = head; } else { // traverse to the end and insert // node at the end and make // it point to the head Node temp = head; while (temp.next != head) { temp = temp.next; } temp.next = new_node; new_node.next = head; } return head;}// Driver codepublic static void main(String args[]) { Node head = null; head = InsertNode(13, head); head = InsertNode(6, head); head = InsertNode(8, head); head = InsertNode(15, head); head = InsertNode(16, head); System.out.print("Initial List: "); DisplayList(head); SumProduct(head);}}// This code is contributed by nishkarsh146 |
Python3
# Python3 implementation to find the # sum and product of all of the Even # Digit sum nodes in a circularly # linked list# Circular list nodeclass Node: def __init__(self, x): self.data = x self.next = None# Function to find the digit sum# for a numberdef digitSum(num): sum = 0 while (num): sum += (num % 10) num //= 10 return sum# 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("List is empty") return # Traverse first to last node else: while (True): # Check if current node's # data has an even digit sum if (not (digitSum(current.data) & 1)): # Calculate sum sum += current.data # Calculate product product *= current.data current = current.next if current == head: break print("Sum =", sum, ", Product = ", product)# Function print the listdef DisplayList(head): current = head # If list is empty simply # show message if (head == None): print("List is empty\n") return # Traverse first to last node else: while True: print(current.data, end = " ") current = current.next if current == head: break# 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 (not newNode): print("Memory Error") return # 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 into # last node link(next) current.next = newNode return head# Driver Codeif __name__ == '__main__': head = None head = InsertNode(head, 13) head = InsertNode(head, 6) head = InsertNode(head, 8) head = InsertNode(head, 15) head = InsertNode(head, 16) print("Initial List: ", end = " ") DisplayList(head) print() SumProduct(head, 11) # This code is contributed by mohit kumar 29 |
C#
// C# implementation to find the sum and // product of all of the Even Digit sum nodes // in a circularly linked list using System;class GFG{// Structure for a nodeclass Node{ public int data; public Node next;}// Function to calculate the sum of// individual digitsstatic int digitSum(int n){ int sum = 0; while (n != 0) { sum += n % 10; n /= 10; } return sum;}// Function to calculate sum and// productstatic void SumProduct(Node head){ Node temp = head; int Sum = 0; int Prod = 1; do { // Check if current node's // data has an even digit sum if (digitSum(temp.data) % 2 == 0) { Sum += temp.data; Prod *= temp.data; } temp = temp.next; } while (temp != head); Console.Write("Sum = " + Sum); Console.Write(", Product = " + Prod);}// Function print the liststatic void DisplayList(Node head){ Node temp = head; if (head != null) { do { // Traverse first to last node Console.Write(temp.data + " "); temp = temp.next; } while (temp != head); } Console.WriteLine();}// Function to insert a node at the ending// of a Circular linked liststatic Node InsertNode(int key, Node head){ // Create a new node Node new_node = new Node(); new_node.data = key; // If linked list is null then // make the first node as head // after insertion if (head == null) { head = new_node; new_node.next = head; } else { // traverse to the end and insert // node at the end and make // it point to the head Node temp = head; while (temp.next != head) { temp = temp.next; } temp.next = new_node; new_node.next = head; } return head;}// Driver codepublic static void Main(String []args) { Node head = null; head = InsertNode(13, head); head = InsertNode(6, head); head = InsertNode(8, head); head = InsertNode(15, head); head = InsertNode(16, head); Console.Write("Initial List: "); DisplayList(head); SumProduct(head);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation to find the sum and// product of all of the Even Digit sum nodes// in a circularly linked listclass Node{ data; next; }// Function to calculate the sum of// individual digitsfunction digitSum(n){ let sum = 0; while (n != 0) { sum += n % 10; n = Math.floor(n/10); } return sum;}// Function to calculate sum and// productfunction SumProduct(head){ let temp = head; let Sum = 0; let Prod = 1; do { // Check if current node's // data has an even digit sum if (digitSum(temp.data) % 2 == 0) { Sum += temp.data; Prod *= temp.data; } temp = temp.next; } while (temp != head); document.write("Sum = " + Sum); document.write(", Product = " + Prod);}// Function print the listfunction DisplayList(head){ let temp = head; if (head != null) { do { // Traverse first to last node document.write(temp.data + " "); temp = temp.next; } while (temp != head); } document.write("<br>");}// Function to insert a node at the ending// of a Circular linked listfunction InsertNode(key,head){ // Create a new node let new_node = new Node(); new_node.data = key; // If linked list is null then // make the first node as head // after insertion if (head == null) { head = new_node; new_node.next = head; } else { // traverse to the end and insert // node at the end and make // it point to the head let temp = head; while (temp.next != head) { temp = temp.next; } temp.next = new_node; new_node.next = head; } return head;}// Driver codelet head = null; head = InsertNode(13, head);head = InsertNode(6, head);head = InsertNode(8, head);head = InsertNode(15, head);head = InsertNode(16, head);document.write("Initial List: ");DisplayList(head);SumProduct(head);// This code is contributed by patel2127</script> |
Output:
Initial List: 13 6 8 15 16 Sum = 42, Product = 9360
Time complexity: O(nlogn) where n is the size of the linked list, log10 is used for calculating the digit sum.
Auxiliary space: O(1) as constant space is being used.
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!