Sum of distances between the two nearest perfect squares to all the nodes of the given linked list in Java
Sum of distances between the two nearest perfect squares to all the nodes of the given linked list in Java
The problem involves calculating the sum of distances between the two nearest perfect squares for all nodes in a linked list. Perfect squares are integers that are the squares of an integer. The distance to a perfect square is the absolute difference between the node's value and the perfect square. The task involves traversing through each node, identifying the nearest perfect squares, computing the distances, and summating the distances. The problem helps improve mathematical calculations and understanding of numbers.
Example:
Input: 1 -> 10 -> 23 -> 7 -> null
Output: 21
Explanation: The given list consists of four nodes: 1, 10, 23, and 7 (nearest perfect squares). Each node has a sum of distances, and the total sum of distances for each node is 21. The sum for each node is 0 + 7 + 9 + 5 = 21, which gives the output of 21. The sums for each node are 0 + 7 + 9 + 5 = 21.
Using Iterative approach
Algorithm
Step 1: Create a linked list with integer values and initialize the sum to 0.
Step 2: Iterate through each node, retrieving the current node's value.
Step 3: Calculate the distance to the nearest perfect squares.
Step 4: Find the nearest perfect squares by calculating the square root of the value.
Step 5: Calculate distances to the lower and upper perfect squares.
Step 6: Sum distances; add the calculated distance for the current node to the total sum.
Step 7: Move to the next node in the linked list.
Step 8: Return the total sum of distances after processing all nodes.
Here is an implementation to find the Sum of distances between the two nearest perfect squares to all the nodes of the given linked list using an iterative approach:
FileName:SumOfDistances.java
class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public class SumOfDistances { public static void main(String[] args) { ListNode head = new ListNode(1); head.next = new ListNode(10); head.next.next = new ListNode(23); head.next.next.next = new ListNode(7); int result = sumOfDistances(head); System.out.println("Sum of distances: " + result); } // Method to calculate the sum of distances to the nearest perfect squares for all nodes public static int sumOfDistances(ListNode head) { int sum = 0; ListNode current = head; while (current != null) { int val = current.val; int distance = sumOfDistancesToNearestPerfectSquares(val); sum += distance; current = current.next; } return sum; } // Method to calculate the sum of distances to the nearest lower and upper perfect squares for a given value private static int sumOfDistancesToNearestPerfectSquares(int val) { int lowerSquare = (int) Math.floor(Math.sqrt(val)); int upperSquare = (int) Math.ceil(Math.sqrt(val)); int lowerDistance = val - (lowerSquare * lowerSquare); int upperDistance = (upperSquare * upperSquare) - val; return lowerDistance + upperDistance; } }
Output:
Sum of distances: 21
Complexity analysis: The above approach has a time complexity of O(n) due to the method'sumOfDistances' traversing the linked list once and a space complexity of O(1) due to the auxiliary space from the recursive stack used by the function calls. The overall space complexity is O(1) due to the inherent linked list storage, which is not counted as additional space used by the algorithm itself.