Replace the values of the nodes with the nearest Prime number
Given the head of a linked list, the task is to replace all the values of the nodes with the nearest prime number. If more than one prime number exists at an equal distance, choose the smallest one.
Examples:
Input: 2 → 6 → 10
Output: 2 → 5 → 11
Explanation: The nearest prime of 2 is 2 itself. The nearest primes of 6 are 5 and 7, since 5 is smaller so, 5 will be chosen. The nearest prime of 10 is 11.Input: 1 → 15 → 20
Output: 2 → 13 → 19
Explanation: The nearest prime of 1 is 2. The nearest primes of 15 are 13 and 17, since 13 is smaller so, 13 will be chosen. The nearest prime of 20 is 19.
Approach: To solve the problem follow the below idea:
Idea is to traverse the Linked List and check if the current number is a prime number, then the number itself is the nearest prime number for it, so no need to replace its value, if the current number is not a prime number, visit both sides of the current number and replace the value with nearest prime number.
Below are the steps for the above approach:
- Initialize a node say, temp = head, to traverse the Linked List.
- Run a loop till temp != NULL,
- Traverse the linked list.
- Initialize three variables num, num1, and num2 with the current node value.
- If the current node value is 1, replace it with 2.
- If the current node is not prime, we have to visit both sides of the number to find the nearest prime number
- and decrease the number by 1 till we get a prime number.
- while (!isPrime(num1)), num1–.
- increase the number by 1 till we get a prime number.
- while (!isPrime(num2)), num2++.
- and decrease the number by 1 till we get a prime number.
- Now update the node value with the nearest prime number.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; class Node { public : int val; Node* next; Node( int num) { val = num; next = NULL; } }; bool isPrime( int n) { if (n == 1) return false ; if (n == 2 || n == 3) return true ; for ( int i = 2; i <= sqrt (n); i++) { if (n % i == 0) { return false ; } } return true ; } Node* primeList(Node* head) { Node* temp = head; while (temp != NULL) { int num = temp->val, num1, num2; num1 = num2 = num; if (num == 1) { temp->val = 2; temp = temp->next; continue ; } while (!isPrime(num1)) { num1--; } while (!isPrime(num2)) { num2++; } if (num - num1 > num2 - num) { temp->val = num2; } else { temp->val = num1; } temp = temp->next; } return head; } // Driver code int main() { Node* head = new Node(2); head->next = new Node(6); head->next->next = new Node(10); Node* ans = primeList(head); while (ans != NULL) { cout << ans->val << " " ; ans = ans->next; } return 0; } |
Java
// Java code for the above approach: import java.util.*; class Node { public int val; public Node next; public Node( int num) { val = num; next = null ; } } class GFG { public static boolean isPrime( int n) { if (n == 1 ) return false ; if (n == 2 || n == 3 ) return true ; for ( int i = 2 ; i <= Math.sqrt(n); i++) { if (n % i == 0 ) { return false ; } } return true ; } public static Node primeList(Node head) { Node temp = head; while (temp != null ) { int num = temp.val, num1, num2; num1 = num2 = num; if (num == 1 ) { temp.val = 2 ; temp = temp.next; continue ; } while (!isPrime(num1)) { num1--; } while (!isPrime(num2)) { num2++; } if (num - num1 > num2 - num) { temp.val = num2; } else { temp.val = num1; } temp = temp.next; } return head; } // Driver code public static void main(String[] args) { Node head = new Node( 2 ); head.next = new Node( 6 ); head.next.next = new Node( 10 ); Node ans = primeList(head); while (ans != null ) { System.out.print(ans.val + " " ); ans = ans.next; } } } // This code is contributed by prasad264 |
Python3
# Python3 code for the above approach: # Import math module to use sqrt function import math # Define a Node class with val and next attributes class Node: def __init__( self , num): self .val = num self . next = None # Define a function to check if a number is prime def is_prime(n): # 1 is not a prime number if n = = 1 : return False # 2 and 3 are prime numbers if n = = 2 or n = = 3 : return True # Check if the number has any factor between 2 and sqrt(n) for i in range ( 2 , int (math.sqrt(n)) + 1 ): if n % i = = 0 : return False return True # Define a function to update the values of the nodes based on prime numbers def prime_list(head): # Set temp variable to head node temp = head # Loop through the linked list while temp ! = None : # Get the value of the current node num = temp.val # Initialize num1 and num2 to num num1, num2 = num, num # If the node value is 1, update it to 2 and move to next node if num = = 1 : temp.val = 2 temp = temp. next continue # Find the nearest prime numbers on either side of num while not is_prime(num1): num1 - = 1 while not is_prime(num2): num2 + = 1 # Update the node value based on which nearest prime is closer to num if num - num1 > num2 - num: temp.val = num2 else : temp.val = num1 # Move to next node temp = temp. next return head # Driver code if __name__ = = '__main__' : # Create a linked list with given node values head = Node( 2 ) head. next = Node( 6 ) head. next . next = Node( 10 ) # Call the function to update the values of nodes ans = prime_list(head) # Print the updated values of nodes in the linked list while ans ! = None : print (ans.val, end = ' ' ) ans = ans. next |
C#
using System; public class Node { public int val; public Node next; public Node( int num) { val = num; next = null ; } } public class Program { public static bool IsPrime( int n) { if (n == 1) return false ; if (n == 2 || n == 3) return true ; for ( int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) { return false ; } } return true ; } public static Node PrimeList(Node head) { Node temp = head; while (temp != null ) { int num = temp.val, num1, num2; num1 = num2 = num; if (num == 1) { temp.val = 2; temp = temp.next; continue ; } while (!IsPrime(num1)) { num1--; } while (!IsPrime(num2)) { num2++; } if (num - num1 > num2 - num) { temp.val = num2; } else { temp.val = num1; } temp = temp.next; } return head; } public static void Main() { Node head = new Node(2); head.next = new Node(6); head.next.next = new Node(10); Node ans = PrimeList(head); while (ans != null ) { Console.Write(ans.val + " " ); ans = ans.next; } } } |
Javascript
// JavaScript code for the above approach: // Node class with val and next attributes class Node { constructor(num) { this .val = num; this .next = null ; } } // function to check if a number is prime function isPrime(n) { // 1 is not a prime number if (n == 1) return false ; // 2 and 3 are prime numbers if (n == 2 || n == 3) return true ; // Check if the number has any factor between 2 and sqrt(n) for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) { return false ; } } return true ; } // function to update the values of the nodes based on prime numbers function primeList(head) { // Set temp variable to head node let temp = head; // Loop through the linked list while (temp != null ) { let num = temp.val, num1, num2; num1 = num2 = num; // If the node value is 1, update it to 2 and move to next node if (num == 1) { temp.val = 2; temp = temp.next; continue ; } // Find the nearest prime numbers on either side of num while (!isPrime(num1)) { num1--; } while (!isPrime(num2)) { num2++; } // Update the node value based on which nearest prime is closer to num if (num - num1 > num2 - num) { temp.val = num2; } else { temp.val = num1; } // move to next node temp = temp.next; } return head; } // Driver code let head = new Node(2); head.next = new Node(6); head.next.next = new Node(10); // Function call let ans = primeList(head); let res = "" while (ans != null ) { res += ans.val; res += " " ; ans = ans.next; } console.log(res); |
2 5 11
Time Complexity: O(sqrt(value of node)), As for each no we are checking the number and its nearest numbers if it is prime.
Auxiliary Space: As we are not using any extra space, the space complexity is O(1).
Approach :
- Define a Node class with val and next attributes.
- Define a function is_prime() to check if a number is prime.
- Define a function prime_list() to update the values of the nodes based on prime numbers:
- a. Loop through the linked list and get the value of the current node.
- b. Initialize num1 and num2 to num.
- c. If the node value is 1, update it to 2 and move to the next node.
- d. Find the nearest prime numbers on either side of num using is_prime() function.
- e. Update the node value based on which nearest prime is closer to num.
- f. Move to the next node.
- g. Return the head node of the updated linked list.
- Create a linked list with given node values.
- Call the function prime_list() to update the values of nodes.
- Print the updated values of nodes in the linked list.
C++
#include <iostream> #include <cmath> using namespace std; class Node { public : int val; Node* next; Node( int num) { val = num; next = NULL; } }; bool is_prime( int n, int * primes, int len) { if (n == 1) { return false ; } for ( int i = 0; i < len; i++) { int p = primes[i]; if (p * p > n) { break ; } if (n % p == 0) { return false ; } } return true ; } Node* prime_list(Node* head) { int max_num = 0; Node* temp = head; while (temp != NULL) { max_num = max(max_num, temp->val); temp = temp->next; } int primes[max_num+1]; primes[0] = 2; int len = 1; for ( int i = 3; i <= sqrt (max_num); i += 2) { if (is_prime(i, primes, len)) { primes[len] = i; len++; } } temp = head; while (temp != NULL) { int num = temp->val; if (num == 1) { temp->val = 2; } else { int num1 = num, num2 = num; while (!is_prime(num1, primes, len)) { num1--; } while (!is_prime(num2, primes, len)) { num2++; } if (num - num1 > num2 - num) { temp->val = num2; } else { temp->val = num1; } } temp = temp->next; } return head; } int main() { Node* head = new Node(2); head->next = new Node(6); head->next->next = new Node(10); Node* ans = prime_list(head); while (ans != NULL) { cout << ans->val << " " ; ans = ans->next; } return 0; } //This code is contributed by Akash Jha |
Java
import java.util.*; class Node { int val; Node next; Node( int num) { val = num; next = null ; } } public class Main { public static boolean is_prime( int n, int [] primes, int len) { if (n == 1 ) { return false ; } for ( int i = 0 ; i < len; i++) { int p = primes[i]; if (p * p > n) { break ; } if (n % p == 0 ) { return false ; } } return true ; } public static Node prime_list(Node head) { int max_num = 0 ; Node temp = head; while (temp != null ) { max_num = Math.max(max_num, temp.val); temp = temp.next; } int [] primes = new int [max_num+ 1 ]; primes[ 0 ] = 2 ; int len = 1 ; for ( int i = 3 ; i <= Math.sqrt(max_num); i += 2 ) { if (is_prime(i, primes, len)) { primes[len] = i; len++; } } temp = head; while (temp != null ) { int num = temp.val; if (num == 1 ) { temp.val = 2 ; } else { int num1 = num, num2 = num; while (!is_prime(num1, primes, len)) { num1--; } while (!is_prime(num2, primes, len)) { num2++; } if (num - num1 > num2 - num) { temp.val = num2; } else { temp.val = num1; } } temp = temp.next; } return head; } public static void main(String[] args) { Node head = new Node( 2 ); head.next = new Node( 6 ); head.next.next = new Node( 10 ); Node ans = prime_list(head); while (ans != null ) { System.out.print(ans.val + " " ); ans = ans.next; } } } //This code is contributed by Akash Jha |
Python3
import math class Node: def __init__( self , num): self .val = num self . next = None def is_prime(n, primes): if n = = 1 : return False for p in primes: if p * p > n: break if n % p = = 0 : return False return True def prime_list(head): max_num = 0 temp = head while temp ! = None : max_num = max (max_num, temp.val) temp = temp. next primes = [ 2 ] for i in range ( 3 , int (math.sqrt(max_num)) + 1 , 2 ): if is_prime(i, primes): primes.append(i) temp = head while temp ! = None : num = temp.val if num = = 1 : temp.val = 2 else : num1, num2 = num, num while not is_prime(num1, primes): num1 - = 1 while not is_prime(num2, primes): num2 + = 1 if num - num1 > num2 - num: temp.val = num2 else : temp.val = num1 temp = temp. next return head if __name__ = = '__main__' : head = Node( 2 ) head. next = Node( 6 ) head. next . next = Node( 10 ) ans = prime_list(head) while ans ! = None : print (ans.val, end = ' ' ) ans = ans. next |
C#
using System; class Node { public int val; public Node next; public Node( int num) { val = num; next = null ; } } class Program { static bool is_prime( int n, int [] primes, int len) { if (n == 1) { return false ; } for ( int i = 0; i < len; i++) { int p = primes[i]; if (p * p > n) { break ; } if (n % p == 0) { return false ; } } return true ; } static Node prime_list(Node head) { int max_num = 0; Node temp = head; while (temp != null ) { max_num = Math.Max(max_num, temp.val); temp = temp.next; } int [] primes = new int [max_num+1]; primes[0] = 2; int len = 1; for ( int i = 3; i <= Math.Sqrt(max_num); i += 2) { if (is_prime(i, primes, len)) { primes[len] = i; len++; } } temp = head; while (temp != null ) { int num = temp.val; if (num == 1) { temp.val = 2; } else { int num1 = num, num2 = num; while (!is_prime(num1, primes, len)) { num1--; } while (!is_prime(num2, primes, len)) { num2++; } if (num - num1 > num2 - num) { temp.val = num2; } else { temp.val = num1; } } temp = temp.next; } return head; } static void Main( string [] args) { Node head = new Node(2); head.next = new Node(6); head.next.next = new Node(10); Node ans = prime_list(head); while (ans != null ) { Console.Write(ans.val + " " ); ans = ans.next; } } } //This code is contributed by Akash Jha |
Javascript
class Node { constructor(num) { this .val = num; this .next = null ; } } function is_prime(n, primes, len) { if (n == 1) { return false ; } for (let i = 0; i < len; i++) { let p = primes[i]; if (p * p > n) { break ; } if (n % p == 0) { return false ; } } return true ; } function prime_list(head) { let max_num = 0; let temp = head; while (temp != null ) { max_num = Math.max(max_num, temp.val); temp = temp.next; } let primes = new Array(max_num+1); primes[0] = 2; let len = 1; for (let i = 3; i <= Math.sqrt(max_num); i += 2) { if (is_prime(i, primes, len)) { primes[len] = i; len++; } } temp = head; while (temp != null ) { let num = temp.val; if (num == 1) { temp.val = 2; } else { let num1 = num, num2 = num; while (!is_prime(num1, primes, len)) { num1--; } while (!is_prime(num2, primes, len)) { num2++; } if (num - num1 > num2 - num) { temp.val = num2; } else { temp.val = num1; } } temp = temp.next; } return head; } let head = new Node(2); head.next = new Node(6); head.next.next = new Node(10); let ans = prime_list(head); while (ans != null ) { console.log(ans.val + " " ); ans = ans.next; } //This code is contributed by Akash Jha |
2 5 11
Time Complexity: In this implementation, we precompute all prime numbers up to the square root of the maximum value in the linked list using a sieve algorithm. Then, for each node in the linked list, we check whether its value is prime or not using the precomputed list of primes. This reduces the time complexity of the algorithm to O(n*log(log(n))), where n is the maximum value in the linked list.
Auxiliary Space: As we are not using any extra space, the space complexity is O(1).
Contact Us