Given a Linked list of N integers, the task is to find the sum of factorials of each prime element in the list.
Examples:
Input: L1 = 4 -> 6 -> 2 -> 12 -> 3
Output: 8
Explanation:
Prime numbers are 2 and 3, hence 2! + 3! = 2 + 6 = 8.
Input: L1 = 7 -> 4 -> 5
Output: 5160
Explanation:
Prime numbers are 7 and 5, hence 7! + 5! = 5160.
Approach: To solve the problem mentioned above follow the steps given below:
- Implement a function factorial(n) that finds the factorial of N .
- Initialize a variable sum = 0. Now, traverse the given list and for each node check whether node is prime or not.
- If node is prime then update sum = sum + factorial(node) otherwise else move the node to next.
- Print the calculated sum in the end.
Below is the implementation of the above approach:
C++
// C++ implementation to fine Sum of// prime factorials in a Linked list#include <bits/stdc++.h>using namespace std;// Node of the singly linked liststruct Node { int data; Node* next;};// Function to insert a node// at the beginning// of the singly 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; // link the old list // off the new node new_node->next = (*head_ref); // move the head to point // to the new node (*head_ref) = new_node;}// Function to return the factorial of Nint factorial(int n){ int f = 1; for (int i = 1; i <= n; i++) { f *= i; } return f;}// Function to check if number is primebool isPrime(int n){ if (n <= 1) return false; if (n <= 3) return true; 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 return the sum of// factorials of the LL elementsint sumFactorial(Node* head_1){ // To store the required sum Node* ptr = head_1; int s = 0; while (ptr != NULL) { // Add factorial of all the elements if (isPrime(ptr->data)) { s += factorial(ptr->data); ptr = ptr->next; } else ptr = ptr->next; } return s;}// Driver codeint main(){ Node* head1 = NULL; push(&head1, 4); push(&head1, 6); push(&head1, 2); push(&head1, 12); push(&head1, 3); cout << sumFactorial(head1); return 0;} |
Java
// Java implementation to find Sum of// prime factorials in a Linked listimport java.util.*;class GFG { // Node of the singly linked list static class Node { int data; Node next; }; // Function to insert a // node at the beginning // of the singly 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 // off 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 return // the factorial of n static int factorial(int n) { int f = 1; for (int i = 1; i <= n; i++) { f *= i; } return f; } // Function to check if number is prime static boolean isPrime(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; 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 return the sum of // factorials of the LL elements static int sumFactorial(Node head_1) { Node ptr = head_1; // To store the required sum int s = 0; while (ptr != null) { // Add factorial of // all the elements if (isPrime(ptr.data)) { s += factorial(ptr.data); ptr = ptr.next; } else { ptr = ptr.next; } } return s; } // Driver Code public static void main(String args[]) { Node head1 = null; head1 = push(head1, 4); head1 = push(head1, 6); head1 = push(head1, 2); head1 = push(head1, 12); head1 = push(head1, 3); int ans = sumFactorial(head1); System.out.println(ans); }} |
Python3
# Python implementation of the approach class Node: def __init__(self, data): self.data = data self.next = next # Function to insert a# node at the beginning # of the singly Linked List def push( head_ref, new_data) : # allocate node new_node = Node(0) # put in the data new_node.data = new_data # link the old list # off the new node new_node.next = (head_ref) # move the head to # point to the new node (head_ref) = new_node return head_ref def factorial(n): f = 1; for i in range(1, n + 1): f *= i; return f; # prime for def def 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 return the sum of # factorials of the LL elements def sumFactorial(head_ref1): # To store the required sum s = 0; ptr1 = head_ref1 while (ptr1 != None) : # Add factorial of all the elements if(isPrime(ptr1.data)): s += factorial(ptr1.data); ptr1 = ptr1.next else: ptr1 = ptr1.next return s; # Driver code # start with the empty list head1 = None# create the linked list head1 = push(head1, 4) head1 = push(head1, 6) head1 = push(head1, 2) head1 = push(head1, 12) head1 = push(head1, 3)ans = sumFactorial(head1)print(ans) |
C#
// C# implementation to find Sum of// prime factorials in a Linked listusing System;class GFG{// Node of the singly linked listclass Node{ public int data; public Node next;};// Function to insert a node // at the beginning of the // singly Linked Liststatic 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 // off 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 return// the factorial of nstatic int factorial(int n){ int f = 1; for(int i = 1; i <= n; i++) { f *= i; } return f;}// Function to check if number// is primestatic bool isPrime(int n){ // Corner cases if (n <= 1) return false; if (n <= 3) return true; 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 return the sum of// factorials of the LL elementsstatic int sumFactorial(Node head_1){ Node ptr = head_1; // To store the required sum int s = 0; while (ptr != null) { // Add factorial of // all the elements if (isPrime(ptr.data)) { s += factorial(ptr.data); ptr = ptr.next; } else { ptr = ptr.next; } } return s;}// Driver Codepublic static void Main(String []args){ Node head1 = null; head1 = push(head1, 4); head1 = push(head1, 6); head1 = push(head1, 2); head1 = push(head1, 12); head1 = push(head1, 3); int ans = sumFactorial(head1); Console.WriteLine(ans);}}// This code is contributed by Amit Katiyar |
Javascript
<script> // JavaScript implementation to find Sum of // prime factorials in a Linked list // Node of the singly linked list class Node { constructor() { this.data = 0; this.next = null; } } // Function to insert a node // at the beginning of the // singly 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 // off 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 return // the factorial of n function factorial(n) { var f = 1; for (var i = 1; i <= n; i++) { f *= i; } return f; } // Function to check if number // is prime function isPrime(n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (var i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Function to return the sum of // factorials of the LL elements function sumFactorial(head_1) { var ptr = head_1; // To store the required sum var s = 0; while (ptr != null) { // Add factorial of // all the elements if (isPrime(ptr.data)) { s += factorial(ptr.data); ptr = ptr.next; } else { ptr = ptr.next; } } return s; } // Driver Code var head1 = null; head1 = push(head1, 4); head1 = push(head1, 6); head1 = push(head1, 2); head1 = push(head1, 12); head1 = push(head1, 3); var ans = sumFactorial(head1); document.write(ans); // This code is contributed by rdtank. </script> |
Output
8
Method 2 (Sieve of Eratosthenes algorithm)
Algorithm
- Define a function factorial(n) that takes an integer n as input
- It returns the factorial of n using a recursive approach, with base cases for n=0 and n=1.
- Define a function sum_of_factorials_of_primes(head) that takes a linked list head as input
- calculates the sum of factorials of all prime elements in the list.
- Initialize a variable max_value to 0
- Traverse the linked list to find the maximum value.
- Set max_value to the maximum value found.
- Generate a list is_prime of boolean values indicating whether each integer up to max_value is prime or not, using the Sieve of Eratosthenes algorithm.
- Initialize a variable sum to 0
- Traverse the linked list again.
- add the factorial of that value to the sum.
- Return the sum.
C++
#include <iostream>#include <vector>#include <cmath>using namespace std;// Defining the linked list nodestruct Node { int val; struct Node* next;};// Function to calculate factorial of a numberint factorial(int n){ if (n == 0 || n == 1) return 1; else return n * factorial(n - 1);}// Function to find sum of factorials of prime elements in linked listint sum_of_factorials_of_primes(struct Node* head){ int max_value = 0; struct Node* current = head; while (current != NULL) { max_value = max(max_value, current->val); current = current->next; } // Using Sieve of Eratosthenes algorithm to pre-calculate all primes up to max_value vector<bool> is_prime(max_value + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i <= sqrt(max_value); i++) { if (is_prime[i]) { for (int j = i * i; j <= max_value; j += i) { is_prime[j] = false; } } } // Calculating the sum of factorials of all prime elements in the linked list int sum = 0; current = head; while (current != NULL) { if (current->val <= max_value && is_prime[current->val]) { sum += factorial(current->val); } current = current->next; } return sum;}int main(){ // Creating the linked list struct Node* head = new Node(); struct Node* second = new Node(); struct Node* third = new Node(); struct Node* fourth = new Node(); struct Node* fifth = new Node(); head->val = 4; head->next = second; second->val = 6; second->next = third; third->val = 2; third->next = fourth; fourth->val = 12; fourth->next = fifth; fifth->val = 3; fifth->next = NULL; // Finding the sum of factorials of prime elements in the linked list int sum = sum_of_factorials_of_primes(head); // Printing the output cout << sum << endl; // Cleaning up the memory delete head; delete second; delete third; delete fourth; delete fifth; return 0;} |
Python3
# function to calculate factorial of a numberdef factorial(n): if n == 0 or n == 1: return 1 else: return n * factorial(n - 1)# function to find sum of factorials of prime elements in linked listdef sum_of_factorials_of_primes(head): max_value = 0 current = head while current != None: max_value = max(max_value, current.val) current = current.next # using Sieve of Eratosthenes algorithm to pre-calculate all primes up to max_value is_prime = [True] * (max_value + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(max_value**0.5) + 1): if is_prime[i]: for j in range(i*i, max_value+1, i): is_prime[j] = False # calculating the sum of factorials of all prime elements in the linked list sum = 0 current = head while current != None: if current.val <= max_value and is_prime[current.val]: sum += factorial(current.val) current = current.next return sum# defining the linked list nodeclass Node: def __init__(self, val=0, next=None): self.val = val self.next = next# creating the linked listhead = Node(4)head.next = Node(6)head.next.next = Node(2)head.next.next.next = Node(12)head.next.next.next.next = Node(3)# finding the sum of factorials of prime elements in the linked listsum = sum_of_factorials_of_primes(head)# printing the outputprint(sum) |
Output
8
Time complexity : O(n*max_value+max_value*log(log(max_value))), where n is the length of the linked list and max_value is the maximum value in the linked list,
Space complexity : O(max_value) for the is_prime list.
