Dada una lista enlazada individualmente que contiene N Nodes, la tarea es encontrar la suma de todos los Nodes posibles de la lista que contiene valor con exactamente tres factores distintos .
Ejemplos:
Entrada: 1 -> 2 -> 4 -> 5
Salida: 4
Explicación:
Los factores de 2 son {1, 2}
Los factores de 3 son {1, 3}
Los factores de 4 son {1, 2, 4}
Los factores de 5 son {1, 5}
Ya que solo 4 contiene tres factores distintos. Por lo tanto, la salida requerida es 4.Entrada: 1 -> 6 -> 8 -> 10
Salida: 0
Enfoque: La idea se basa en el hecho de que si un número es un número primo , entonces el cuadrado del número contiene exactamente tres factores distintos . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos nodeSum , para almacenar la suma de Nodes que contiene valor con exactamente tres factores distintos.
- Recorra la lista enlazada y para cada Node, verifique si la raíz cuadrada de los Nodes actuales es un número primo o no. Si se encuentra que es cierto, entonces incremente nodeSum por el valor del Node actual.
- Finalmente, imprima el valor de nodeSum .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a
// singly Linked List
struct Node {
// Stores data value
// of a Node
int data;
// Stores pointer
// to next Node
struct Node* next;
};
// Function to insert a node at the
// beginning of the singly Linked List
void push(Node** head_ref,
int new_data)
{
// Create a new Node
Node* new_node = new Node;
// Insert the data into
// the Node
new_node->data = new_data;
// Insert pointer to
// the next Node
new_node->next = (*head_ref);
// Update head_ref
(*head_ref) = new_node;
}
// Function to check if a number
// is a prime number or not
bool CheckPrimeNumber(int n)
{
// Base Case
if (n <= 1)
return false;
if (n <= 3)
return true;
// If n is multiple of 2 or 3
if (n % 2 == 0 || n % 3 == 0)
return false;
// Iterate over the range
// [5, sqrt(N)]
for (int i = 5; i * i <= n;
i = i + 6) {
// If n is multiple of
// i or (i + 2)
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
// Function to check if number is
// a perfect square number or not
bool checkperfect_square(int n)
{
// Stores square root of n
long double sr = sqrt(n);
// If n is a
// perfect square number
if (sr - floor(sr) == 0) {
return true;
}
return false;
}
// Function to check if n is square
// of a prime number or not
bool is_square(int n)
{
// If n is a perfect square
if (checkperfect_square(n)) {
// Stores sqrt of n
int root = sqrt(n);
// If root is a prime number
if (CheckPrimeNumber(root)) {
return true;
}
}
return false;
}
// Function to find sum of node values
// which contains three distinct factors
int calculate_sum(struct Node* head)
{
// Stores head of
// the linked list
Node* curr = head;
// Stores sum of nodes whose data value
// contains three distinct factors
int nodeSum = 0;
// Traverse the linked list
while (curr) {
// If data value of curr is
// square of a prime number
if (is_square(curr->data)) {
// Update nodeSum
nodeSum += curr->data;
}
// Update curr
curr = curr->next;
}
// Return sum
return nodeSum;
}
// Driver Code
int main()
{
// Stores head node of
// the linked list
Node* head = NULL;
// Insert all data values
// in the linked list
push(&head, 5);
push(&head, 4);
push(&head, 2);
push(&head, 1);
cout << calculate_sum(head);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Structure of a
// singly Linked List
static class Node
{
// Stores data value
// of a Node
int data;
// Stores pointer
// to next Node
Node next;
};
static Node head = null;
// Function to insert a node at the
// beginning of the singly Linked List
static Node push(int new_data)
{
// Create a new Node
Node new_node = new Node();
// Insert the data into
// the Node
new_node.data = new_data;
// Insert pointer to
// the next Node
new_node.next = head;
// Update head_ref
return head = new_node;
}
// Function to check if a number
// is a prime number or not
static boolean CheckPrimeNumber(int n)
{
// Base Case
if (n <= 1)
return false;
if (n <= 3)
return true;
// If n is multiple of 2 or 3
if (n % 2 == 0 || n % 3 == 0)
return false;
// Iterate over the range
// [5, Math.sqrt(N)]
for(int i = 5; i * i <= n; i = i + 6)
{
// If n is multiple of
// i or (i + 2)
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
// Function to check if number is
// a perfect square number or not
static boolean checkperfect_square(int n)
{
// Stores square root of n
long sr = (long)Math.sqrt(n);
// If n is a
// perfect square number
if (sr - Math.floor(sr) == 0)
{
return true;
}
return false;
}
// Function to check if n is square
// of a prime number or not
static boolean is_square(int n)
{
// If n is a perfect square
if (checkperfect_square(n))
{
// Stores sqrt of n
int root = (int)Math.sqrt(n);
// If root is a prime number
if (CheckPrimeNumber(root))
{
return true;
}
}
return false;
}
// Function to find sum of node values
// which contains three distinct factors
static int calculate_sum(Node head)
{
// Stores head of
// the linked list
Node curr = head;
// Stores sum of nodes whose data value
// contains three distinct factors
int nodeSum = 0;
// Traverse the linked list
while (curr.next != null)
{
// If data value of curr is
// square of a prime number
if (is_square(curr.data))
{
// Update nodeSum
nodeSum += curr.data;
}
// Update curr
curr = curr.next;
}
// Return sum
return nodeSum;
}
// Driver Code
public static void main(String[] args)
{
// Stores head node of
// the linked list
// Insert all data values
// in the linked list
head = push(5);
head = push(4);
head = push(2);
head = push(1);
System.out.print(calculate_sum(head));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to implement # the above approach import math # Structure of a # singly linked list class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None # Function to insert a nodeat the # beginning of the singly linked list def Push(self, new_data): # Create new node # and insert the data # into the node new_node = Node(new_data) # Insert pointer to the # next node new_node.next = self.head # Update head self.head = new_node # Function to find sum of node values # which contains three distinct factors def calculate_sum(self): # Stores the head of linked list curr = self.head # Stores sum of nodes whose data # value contains three distinct factors nodeSum = 0 # Traverse the linked list while(curr): # If data value of curr is # square of a prime number if (is_square(curr.data)): # Update nodeSum nodeSum += curr.data # Update curr curr = curr.next # Return Sum return nodeSum # Function to check if a number # is a prime number or not def CheckPrimeNumber(n): # Base Class if n <= 1: return False if n <= 3: return True # If n is multiple of 2 or 3 if (n % 2 == 0 or n % 3 == 0): return False # Iterate over the range # [5,sqrt(N)] i = 5 while ((i * i) <= n): # If n is multiple of # i or (i+2) if (n % i == 0 or n % (i + 2) == 0): return False i += 6 return True # Function to check if number is # a perfect square number or not def checkperfect_square(n): # Stores square root of n sr = math.sqrt(n) # If n is a perfect # square number if (sr - math.floor(sr)) == 0: return True return False # Function to check if n is square # of a prime number or not def is_square(n): # If n is a perfect square if (checkperfect_square(n)): # Stores sqrt of n root = math.sqrt(n) # If root is a prime number if (CheckPrimeNumber(root)): return True return False # Driver Code if __name__ == "__main__" : LList = LinkedList() # Insert all data values # in the linked list LList.Push(5) LList.Push(4) LList.Push(2) LList.Push(1) print(LList.calculate_sum()) # This code is contributed by Virusbuddah
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Structure of a
// singly Linked List
public class Node
{
// Stores data value
// of a Node
public int data;
// Stores pointer
// to next Node
public Node next;
};
static Node head = null;
// Function to insert a node at the
// beginning of the singly Linked List
static Node push(int new_data)
{
// Create a new Node
Node new_node = new Node();
// Insert the data into
// the Node
new_node.data = new_data;
// Insert pointer to
// the next Node
new_node.next = head;
// Update head_ref
return head = new_node;
}
// Function to check if a number
// is a prime number or not
static bool CheckPrimeNumber(int n)
{
// Base Case
if (n <= 1)
return false;
if (n <= 3)
return true;
// If n is multiple of 2 or 3
if (n % 2 == 0 || n % 3 == 0)
return false;
// Iterate over the range
// [5, Math.Sqrt(N)]
for(int i = 5; i * i <= n; i = i + 6)
{
// If n is multiple of
// i or (i + 2)
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
// Function to check if number is
// a perfect square number or not
static bool checkperfect_square(int n)
{
// Stores square root of n
long sr = (long)Math.Sqrt(n);
// If n is a perfect square number
if (sr - Math.Floor((double)sr) == 0)
{
return true;
}
return false;
}
// Function to check if n is square
// of a prime number or not
static bool is_square(int n)
{
// If n is a perfect square
if (checkperfect_square(n))
{
// Stores sqrt of n
int root = (int)Math.Sqrt(n);
// If root is a prime number
if (CheckPrimeNumber(root))
{
return true;
}
}
return false;
}
// Function to find sum of node values
// which contains three distinct factors
static int calculate_sum(Node head)
{
// Stores head of
// the linked list
Node curr = head;
// Stores sum of nodes whose data value
// contains three distinct factors
int nodeSum = 0;
// Traverse the linked list
while (curr.next != null)
{
// If data value of curr is
// square of a prime number
if (is_square(curr.data))
{
// Update nodeSum
nodeSum += curr.data;
}
// Update curr
curr = curr.next;
}
// Return sum
return nodeSum;
}
// Driver Code
public static void Main(String[] args)
{
// Stores head node of
// the linked list
// Insert all data values
// in the linked list
head = push(5);
head = push(4);
head = push(2);
head = push(1);
Console.Write(calculate_sum(head));
}
}
// This code is contributed by aashish1995
Javascript
<script>
// JavaScript program to implement
// the above approach
// Structure of a
// singly Linked List
class Node
{
constructor()
{
// Stores data value
// of a Node
this.data = 0;
// Stores pointer
// to next Node
this.next = null;
}
};
var head = null;
// Function to insert a node at the
// beginning of the singly Linked List
function push(new_data)
{
// Create a new Node
var new_node = new Node();
// Insert the data into
// the Node
new_node.data = new_data;
// Insert pointer to
// the next Node
new_node.next = head;
// Update head_ref
return head = new_node;
}
// Function to check if a number
// is a prime number or not
function CheckPrimeNumber(n)
{
// Base Case
if (n <= 1)
return false;
if (n <= 3)
return true;
// If n is multiple of 2 or 3
if (n % 2 == 0 || n % 3 == 0)
return false;
// Iterate over the range
// [5, Math.Sqrt(N)]
for(var i = 5; i * i <= n; i = i + 6)
{
// If n is multiple of
// i or (i + 2)
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
// Function to check if number is
// a perfect square number or not
function checkperfect_square(n)
{
// Stores square root of n
var sr = Math.sqrt(n);
// If n is a perfect square number
if (sr - Math.floor(sr) == 0)
{
return true;
}
return false;
}
// Function to check if n is square
// of a prime number or not
function is_square(n)
{
// If n is a perfect square
if (checkperfect_square(n))
{
// Stores sqrt of n
var root = Math.sqrt(n);
// If root is a prime number
if (CheckPrimeNumber(root))
{
return true;
}
}
return false;
}
// Function to find sum of node values
// which contains three distinct factors
function calculate_sum(head)
{
// Stores head of
// the linked list
var curr = head;
// Stores sum of nodes whose data value
// contains three distinct factors
var nodeSum = 0;
// Traverse the linked list
while (curr.next != null)
{
// If data value of curr is
// square of a prime number
if (is_square(curr.data))
{
// Update nodeSum
nodeSum += curr.data;
}
// Update curr
curr = curr.next;
}
// Return sum
return nodeSum;
}
// Driver Code
// Stores head node of
// the linked list
// Insert all data values
// in the linked list
head = push(5);
head = push(4);
head = push(2);
head = push(1);
document.write(calculate_sum(head));
</script>
Producción:
4
Complejidad de tiempo: O(N * √ X), donde X es el elemento más grande en la lista enlazada
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kothawade29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA