Сумма факториалов простых чисел в связанном списке

Опубликовано: 7 Января, 2022

Учитывая связанный список из N целых чисел, задача состоит в том, чтобы найти сумму факториалов каждого простого элемента в списке.

Примеры:

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.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: Чтобы решить указанную выше проблему, выполните следующие действия:

Реализуйте функцию factorial (n), которая находит факториал N.
Инициализировать переменную sum = 0 . Теперь просмотрите данный список и для каждого узла проверьте, является ли узел простым или нет.
Если узел является простым, обновите сумму = сумма + факториал (узел), иначе переместите узел к следующему.
В конце выведите рассчитанную сумму.

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 list
struct Node {
    int data;
    Node* next;
};
  
// Function to insert a node
// at the beginning
// of the singly Linked List
void 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 N
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
bool 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 elements
int 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 code
int 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 list
  
import 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 list
using System;
  
class GFG{
  
// Node of the singly linked list
class Node
{
    public int data;
    public 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 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 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;
  
  &
            

                    
                                            Python
                                            C++
                                            Java
                                            Школьное программирование
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИКак научиться программировать на Python
6 Июля, 2023
Количество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Максимизируйте число из заданных целых чисел, используя следующие операции
27 Февраля, 2023
Максимизируйте частоту элемента, добавив X в подпоследовательность
26 Февраля, 2023
Элемент поиска в матрице
26 Февраля, 2023
Минимизируйте вставку 0 или 1, чтобы ни одна соседняя пара не имела одинакового значения
25 Февраля, 2023
XOR всех элементов массива, которые являются идеальными квадратами
25 Февраля, 2023
Найдите минимум конфет, оставшихся после соблюдения заданных правил.
25 Февраля, 2023


    


        
            
                
                    
                        
                        < PROGLER >
                    
                
                
                    
                        Общее
                        
                        Контакты
                        Политика конфиденциальности
                    
                    
                        Обучение
                        Блог
                    
                
            
            
                © progler.ru 2024. Все права защищены.