Given a singly linked list containing N nodes, the task is to find the sum of all possible nodes of the list which contains value with exactly three distinct factors.
Examples:
Input: 1 -> 2 -> 4 -> 5
Output: 4
Explanation:
Factors of 2 are {1, 2}
Factors of 3 are {1, 3}
Factors of 4 are {1, 2, 4}
Factors of 5 are {1, 5}
Since only 4 contains three distinct factors. Therefore, the required output is 4.Input: 1 -> 6 -> 8 -> 10
Output: 0
Approach: The idea is based on the fact that if a number is a prime number, then the square of the number contains exactly three distinct factors. Follow the steps below to solve the problem:
- Initialize a variable, say nodeSum, to store the sum of nodes which contains value with exactly three distinct factors.
- Traverse the linked list and for each node, check if the square root of the current nodes is a prime number or not. If found to be true, then increment nodeSum by the value of current node.
- Finally, print the value of nodeSum.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Structure of a// singly Linked Liststruct 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 Listvoid 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 notbool 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 notbool 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 notbool 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 factorsint 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 Codeint 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 approachimport java.util.*;class GFG{// Structure of a// singly Linked Liststatic 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 Liststatic 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 notstatic 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 notstatic 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 notstatic 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 factorsstatic 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 Codepublic 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 approachimport math# Structure of a# singly linked listclass 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 notdef 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 notdef 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 approachusing System;class GFG{// Structure of a// singly Linked Listpublic 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 Liststatic 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 notstatic 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 notstatic 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 notstatic 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 factorsstatic 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 Codepublic 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 Listclass 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 Listfunction 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 notfunction 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 notfunction 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 notfunction 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 factorsfunction 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 listhead = push(5);head = push(4);head = push(2);head = push(1);document.write(calculate_sum(head));</script> |
Output:
4
Time Complexity: O(N * √ X), where X is the largest element in the linked list
Auxiliary Space: O(1)
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!
