Given a doubly linked list containing N nodes. The task is to find the product of all prime nodes.
Example:
Input: List = 15 <=> 16 <=> 6 <=> 7 <=> 17
Output: Product of Prime Nodes: 119Input: List = 5 <=> 3 <=> 4 <=> 2 <=> 9
Output: Product of Prime Nodes: 30
Approach:
- Initialize a pointer temp with the head of the linked list and a product variable with 1.
- Start traversing the linked list using a loop until all the nodes get traversed.
- If node value is prime then multiply the value of the current node to the product i.e. product *= current_node-> data.
- Increment the pointer to the next node of linked list i.e. temp = temp -> next.
- Return the product.
Below is the implementation of the above approach:
C++
// C++ implementation to product all// prime nodes from the doubly// linked list#include <bits/stdc++.h>using namespace std;// Node of the doubly linked liststruct Node { int data; Node *prev, *next;};// function to insert a node at the beginning// of the Doubly Linked Listvoid push(Node** head_ref, int new_data){ // allocate node Node* new_node = (Node*)malloc(sizeof(struct Node)); // put in the data new_node->data = new_data; // since we are adding at the beginning, // prev is always NULL new_node->prev = NULL; // link the old list of the new node new_node->next = (*head_ref); // change prev of head node to new node if ((*head_ref) != NULL) (*head_ref)->prev = new_node; // move the head to point to the new node (*head_ref) = new_node;}// Function to check if a number is primebool isPrime(int n){ // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true;}// function to product all prime nodes// from the doubly linked listint prodOfPrime(Node** head_ref){ Node* ptr = *head_ref; Node* next; // variable prod = 1 for multiplying nodes value int prod = 1; // traverse list till last node while (ptr != NULL) { next = ptr->next; // if number is prime then // multiply to product if (isPrime(ptr->data)) prod = prod * ptr->data; ptr = next; } // return product return prod;}// Driver programint main(){ // start with the empty list Node* head = NULL; // create the doubly linked list // 15 <-> 16 <-> 7 <-> 6 <-> 17 push(&head, 17); push(&head, 6); push(&head, 7); push(&head, 16); push(&head, 15); int prod = prodOfPrime(&head); cout << "Product of Prime Nodes : " << prod; return 0;} |
Java
// Java implementation to product all// prime nodes from the doubly// linked list// Node of the doubly linked listclass Node{ int data; Node next, prev; Node(int d) { data = d; next = null; prev = null; }}class DLL { // function to insert a node at the beginning // of the Doubly Linked List static Node push(Node head, int data) { Node newNode = new Node(data); newNode.next = head; newNode.prev = null; if (head != null) head.prev = newNode; head = newNode; return head; } // Function to check if a number is prime static boolean isPrime(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // function to product all prime nodes // from the doubly linked list static int prodOfPrime(Node node) { // variable prod = 1 for multiplying nodes value int prod = 1; // traverse list till last node while (node != null) { // check is node value is Prime // if true then multiply to prod if (isPrime(node.data)) prod *= node.data; node = node.next; } // return product return prod; } // Driver Program public static void main(String[] args) { // Start with empty list Node head = null; // create the doubly linked list // 15 <-> 16 <-> 7 <-> 6 <-> 17 head = push(head, 17); head = push(head, 7); head = push(head, 6); head = push(head, 9); head = push(head, 10); head = push(head, 16); head = push(head, 15); int prod = prodOfPrime(head); System.out.println("Product of Prime Nodes: " + prod); }}// This code is contributed by Vivekkumar Singh |
Python3
# Python3 implementation to product all# prime nodes from the doubly# linked list# Node of the doubly linked list class Node: def __init__(self, data): self.data = data self.prev = None self.next = None# function to insert a node at the beginning# of the Doubly Linked Listdef push(head_ref, new_data): # allocate node new_node = Node(0) # put in the data new_node.data = new_data # since we are multiplying at the beginning, # prev is always None new_node.prev = None # link the old list of the new node new_node.next = (head_ref) # change prev of head node to new node if ((head_ref) != None): (head_ref).prev = new_node # move the head to point to the new node (head_ref) = new_node return head_ref# Function to check if a number is primedef isPrime(n): # Corner cases if (n <= 1): return False if (n <= 3): return True # This is checked so that we can skip # middle five numbers in below loop if (n % 2 == 0 or n % 3 == 0): return False i = 5 while ( i * i <= n ): if (n % i == 0 or n % (i + 2) == 0): return False i += 6; return True# function to product all prime nodes# from the doubly linked listdef prodOfPrime(head_ref): ptr = head_ref next = None # variable prod = 1 for multiplying nodes value prod = 1 # traverse list till last node while (ptr != None): next = ptr.next # if number is prime then # multiply to product if (isPrime(ptr.data)): prod = prod * ptr.data ptr = next # return product return prod# Driver Codeif __name__ == "__main__": # start with the empty list head = None # create the doubly linked list # 15 <. 16 <. 7 <. 6 <. 17 head = push(head, 17) head = push(head, 6) head = push(head, 7) head = push(head, 16) head = push(head, 15) prod = prodOfPrime(head) print("Product of Prime Nodes : ", prod)# This code is contributed by Arnab Kundu |
C#
// C# implementation to product all // prime nodes from the doubly // linked list using System;// Node of the doubly linked list public class Node { public int data; public Node next, prev; public Node(int d) { data = d; next = null; prev = null; } } class DLL { // function to insert a node at the beginning // of the Doubly Linked List static Node push(Node head, int data) { Node newNode = new Node(data); newNode.next = head; newNode.prev = null; if (head != null) head.prev = newNode; head = newNode; return head; } // Function to check if a number is prime static Boolean isPrime(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // function to product all prime nodes // from the doubly linked list static int prodOfPrime(Node node) { // variable prod = 1 for multiplying nodes value int prod = 1; // traverse list till last node while (node != null) { // check is node value is Prime // if true then multiply to prod if (isPrime(node.data)) prod *= node.data; node = node.next; } // return product return prod; } // Driver code public static void Main(String []args) { // Start with empty list Node head = null; // create the doubly linked list // 15 <-> 16 <-> 7 <-> 6 <-> 17 head = push(head, 17); head = push(head, 7); head = push(head, 6); head = push(head, 9); head = push(head, 10); head = push(head, 16); head = push(head, 15); int prod = prodOfPrime(head); Console.WriteLine("Product of Prime Nodes: " + prod); } } // This code is contributed by Arnab Kundu |
Javascript
<script>// JavaScript implementation to product all// prime nodes from the doubly// linked list// Node of the doubly linked listclass Node { constructor(val) { this.data = val; this.prev = null; this.next = null; }} // function to insert a node at the beginning // of the Doubly Linked List function push(head , data) { var newNode = new Node(data); newNode.next = head; newNode.prev = null; if (head != null) head.prev = newNode; head = newNode; return head; } // Function to check if a number is prime function isPrime(n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; for (i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // function to product all prime nodes // from the doubly linked list function prodOfPrime(node) { // variable prod = 1 for multiplying nodes value var prod = 1; // traverse list till last node while (node != null) { // check is node value is Prime // if true then multiply to prod if (isPrime(node.data)) prod *= node.data; node = node.next; } // return product return prod; } // Driver Program // Start with empty list var head = null; // create the doubly linked list // 15 <-> 16 <-> 7 <-> 6 <-> 17 head = push(head, 17); head = push(head, 7); head = push(head, 6); head = push(head, 9); head = push(head, 10); head = push(head, 16); head = push(head, 15); var prod = prodOfPrime(head); document.write("Product of Prime Nodes: " + prod);// This code contributed by umadevi9616</script> |
Output
Product of Prime Nodes : 119
Complexity Analysis:
- Time Complexity: O(N), where N is the number of nodes.
- Space Complexity: O(1) because using constant variables
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]
[…] Information to that Topic: geeksforgeeks.org/product-of-all-prime-nodes-in-a-doubly-linked-list/ […]