Product of Smallest and Largest prime numbers in a Linked List
INTRODUCTION:-
A linked list is a data structure that consists of a sequence of elements called nodes. Each node in the linked list contains a data element and a reference to the next node in the sequence. Linked lists are commonly used in computer programming for a variety of applications, including the implementation of dynamic data structures, such as stacks, queues, and hash tables.
In this article, we will discuss how to find the product of the smallest and largest prime numbers in a linked list.
APPROACH:-
The problem can be solved by iterating through the linked list and identifying the prime numbers. Once the prime numbers have been identified, the smallest and largest prime numbers can be determined, and their product can be calculated.
To solve this problem, we will need to define two helper functions: isPrime and getMaxNode.
The isPrime function takes an integer as input and returns true if the number is prime and false otherwise. The function works by checking whether the input number is divisible by any number between 2 and the square root of the input number.
The getMaxNode function takes a linked list as input and returns the node with the largest data element. The function works by iterating through the linked list and keeping track of the node with the largest data element.
With these helper functions in place, we can now write the main function to solve the problem. The function will take a linked list as input and return the product of the smallest and largest prime numbers in the list.
ALGORITHM:-
Here is the algorithm for the main function:
- Initialize a variable smallestPrime to infinity and largestPrime to zero.
- Initialize a variable currentNode to the head of the linked list.
- Iterate through the linked list.
- For each node, check if the data element is prime using the isPrime function.
- If the data element is prime, check if it is smaller than smallestPrime or larger than largestPrime. If so, update smallestPrime or largestPrime accordingly.
- Set currentNode to the next node in the linked list.
- Once the iteration is complete, return the product of smallestPrime and largestPrime.
Given a Linked list of integers, find the product of the smallest and largest prime numbers present in the list.
Input: 11 -> 8 -> 15 -> 3 -> 10 -> 21
Output: 33
Explanation: The smallest prime number is 3 and the largest prime number is 11. The product of 3 and 11 is 33.Input: 1 -> 7 -> 6 -> 8 -> 9 -> 5
Output: 35
Explanation: The smallest prime number is 5 and the largest prime number is 7. The product of 5 and 7 is 35.
EXAMPLE:-
Lets look on the example of an input:11->8->15->3->10->21.
In C++, JAVA, PYTHON AND C#.
Below is the code for the above approach:
C++
// C++ Implementation #include <iostream> using namespace std; // Linked list node struct Node { int data; struct Node* next; Node( int x) { data = x; next = NULL; } }; // Function to check whether a number is // prime or not bool isPrime( int n) { if (n <= 1) return false ; for ( int i = 2; i * i <= n; i++) if (n % i == 0) return false ; return true ; } // Function to find the product of // smallest and largest prime numbers // in a linked list int productOfSmallestAndLargestPrimes(Node* head) { int smallest = -1, largest = -1; while (head != NULL) { if (isPrime(head->data)) { if (smallest == -1 || head->data < smallest) { smallest = head->data; } if (largest == -1 || head->data > largest) { largest = head->data; } } head = head->next; } if (smallest == -1 || largest == -1) { return -1; } return smallest * largest; } // Driver code int main() { Node* head = new Node(11); head->next = new Node(8); head->next->next = new Node(15); head->next->next->next = new Node(3); head->next->next->next->next = new Node(10); head->next->next->next->next->next = new Node(21); // Function call cout << productOfSmallestAndLargestPrimes(head) << endl; return 0; } |
Java
public class Node { int data; Node next; public Node( int data) { this .data = data; this .next = null ; } } class LinkedList { Node head; public LinkedList() { this .head = null ; } public void addNode( int data) { Node newNode = new Node(data); if ( this .head == null ) { this .head = newNode; } else { Node currentNode = this .head; while (currentNode.next != null ) { currentNode = currentNode.next; } currentNode.next = newNode; } } } class Main { public static boolean isPrime( int n) { if (n < 2 ) { return false ; } for ( int i = 2 ; i <= Math.sqrt(n); i++) { if (n % i == 0 ) { return false ; } } return true ; } public static int productOfSmallestAndLargestPrime(LinkedList linkedList) { int smallestPrime = Integer.MAX_VALUE; int largestPrime = 0 ; Node currentNode = linkedList.head; while (currentNode != null ) { if (isPrime(currentNode.data)) { if (currentNode.data < smallestPrime) { smallestPrime = currentNode.data; } if (currentNode.data > largestPrime) { largestPrime = currentNode.data; } } currentNode = currentNode.next; } return smallestPrime * largestPrime; } public static void main(String[] args) { LinkedList linkedList = new LinkedList(); linkedList.addNode( 11 ); linkedList.addNode( 8 ); linkedList.addNode( 15 ); linkedList.addNode( 3 ); linkedList.addNode( 10 ); linkedList.addNode( 21 ); int product = productOfSmallestAndLargestPrime(linkedList); System.out.println(product); //output=33 } } |
Python
class Node: def __init__( self , data): self .data = data self . next = None class LinkedList: def __init__( self ): self .head = None def addNode( self , data): newNode = Node(data) if self .head is None : self .head = newNode else : currentNode = self .head while currentNode. next is not None : currentNode = currentNode. next currentNode. next = newNode def isPrime(n): if n < 2 : return False for i in range ( 2 , int (n * * 0.5 ) + 1 ): if n % i = = 0 : return False return True def productOfSmallestAndLargestPrime(linkedList): smallestPrime = float ( 'inf' ) largestPrime = 0 currentNode = linkedList.head while currentNode is not None : if isPrime(currentNode.data): if currentNode.data < smallestPrime: smallestPrime = currentNode.data if currentNode.data > largestPrime: largestPrime = currentNode.data currentNode = currentNode. next return smallestPrime * largestPrime linkedList = LinkedList() linkedList.addNode( 11 ) linkedList.addNode( 8 ) linkedList.addNode( 15 ) linkedList.addNode( 3 ) linkedList.addNode( 10 ) linkedList.addNode( 21 ) product = productOfSmallestAndLargestPrime(linkedList) print (product) |
C#
// C# Implementation using System; // Linked list node public class Node { public int data; public Node next; public Node( int x) { data = x; next = null ; } } public class GFG { // Function to check whether a number is prime or not public static bool IsPrime( int n) { if (n <= 1) return false ; for ( int i = 2; i * i <= n; i++) { if (n % i == 0) return false ; } return true ; } // Function to find the product of smallest and largest // prime numbers in a linked list public static int ProductOfSmallestAndLargestPrimes(Node head) { int smallest = -1, largest = -1; while (head != null ) { if (IsPrime(head.data)) { if (smallest == -1 || head.data < smallest) { smallest = head.data; } if (largest == -1 || head.data > largest) { largest = head.data; } } head = head.next; } if (smallest == -1 || largest == -1) { return -1; } return smallest * largest; } // Driver code public static void Main( string [] args) { Node head = new Node(11); head.next = new Node(8); head.next.next = new Node(15); head.next.next.next = new Node(3); head.next.next.next.next = new Node(10); head.next.next.next.next.next = new Node(21); // Function call Console.WriteLine( ProductOfSmallestAndLargestPrimes(head)); } } // This code is contributed by Susobhan Akhuli |
Javascript
<script> // JavaScript Implementation // Linked list node class Node { constructor(x) { this .data = x; this .next = null ; } } // Function to check whether a number is prime or not function isPrime(n) { if (n <= 1) { return false ; } for (let i = 2; i * i <= n; i++) { if (n % i === 0) { return false ; } } return true ; } // Function to find the product of smallest and largest prime numbers in a linked list function productOfSmallestAndLargestPrimes(head) { let smallest = -1; let largest = -1; let current = head; while (current !== null ) { if (isPrime(current.data)) { if (smallest === -1 || current.data < smallest) { smallest = current.data; } if (largest === -1 || current.data > largest) { largest = current.data; } } current = current.next; } if (smallest === -1 || largest === -1) { return -1; } return smallest * largest; } const head = new Node(11); head.next = new Node(8); head.next.next = new Node(15); head.next.next.next = new Node(3); head.next.next.next.next = new Node(10); head.next.next.next.next.next = new Node(21); // Function call document.write(productOfSmallestAndLargestPrimes(head)); // This code is contributed by Susobhan Akhuli </script> |
33
TIME COMPLEXITY:-
It is important to note that the time complexity of this algorithm is O(n*sqrt(n)), where n is the number of nodes in the linked list. This is because we need to iterate through each node in the linked list and check whether it is prime, which takes O(sqrt(n)) time for each node.
Time Complexity: O(n*sqrt(n)), where n is the length of the linked list
Auxiliary Space: O(1)
CONCLUSION:-
In conclusion, we have discussed how to find the product of the smallest and largest prime numbers in a linked list. This problem can be solved by iterating through the linked list and identifying the prime numbers. Once the prime numbers have been identified, the smallest and largest prime numbers can be determined, and their product can be calculated. By defining two helper functions and using them in the main function, we can solve this problem efficiently.