Сумма расстояний между двумя ближайшими точными квадратами до всех узлов данного связного списка
Учитывая связанный список, задача состоит в том, чтобы найти сумму расстояний между двумя ближайшими точными квадратами для всех узлов данного связанного списка.
Примеры:
Input: 3 -> 15 -> 7 -> NULL
Output: 15
For 3: closest left perfect square is 1 and closest right 4 i.e. 4-1 = 3
For 15: 16 – 9 = 7
For 7: 9 – 4 = 5
3 + 7 + 5 = 15
Input: 1 -> 5 -> 10 -> 78 -> 23 -> NULL
Output: 38
Approach: Initialise sum = 0 and for every node, if the current node’s value is a perfect square itself then the left and right closest perfect square will be the value itself and distance will be 0. Else, find the left and right closest perfect squares say leftPS and rightPS and update sum = sum + (rightPS – leftPS).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Structure of a node of linked list class Node { public : int data; Node* next; Node( int data) { this ->data = data; this ->next = NULL; } }; // Function to find the total distance sum int distanceSum(Node* head) { // If head is null if (head == NULL) return 0; // To store the required sum int tsum = 0; Node* temp = head; // Traversing through all the nodes one by one while (temp != NULL) { double sq_root = sqrt (temp->data); // If current node is not a perfect square // then find left perfect square and // right perfect square if (sq_root < temp->data) { int left_ps = ( int ) floor (sq_root) * ( int ) floor (sq_root); int right_ps = ( int ) ceil (sq_root) * ( int ) ceil (sq_root); tsum += right_ps - left_ps; } // Get to the next node temp = temp->next; } return tsum; } // Driver code int main() { Node* head = new Node(3); head->next = new Node(15); head->next->next = new Node(7); head->next->next->next = new Node(40); head->next->next->next->next = new Node(42); int result = distanceSum(head); cout << result << endl; return 0; } // This code is contributed by divyeshrabadiya07 |
Java
// Java implementation of the approach class GFG { // Structure of a node of linked list static class Node { int data; Node next; Node( int data) { this .data = data; this .next = null ; } } // Function to find the total distance sum static int distanceSum(Node head) { // If head is null if (head == null ) return 0 ; // To store the required sum int tsum = 0 ; Node temp = head; // Traversing through all the nodes one by one while (temp != null ) { double sq_root = Math.sqrt(temp.data); // If current node is not a perfect square // then find left perfect square and // right perfect square if (sq_root < temp.data) { int left_ps = ( int )Math.floor(sq_root) * ( int )Math.floor(sq_root); int right_ps = ( int )Math.ceil(sq_root) * ( int )Math.ceil(sq_root); tsum += right_ps - left_ps; } // Get to the next node temp = temp.next; } return tsum; } // Driver code public static void main(String[] args) { Node head = new Node( 3 ); head.next = new Node( 15 ); head.next.next = new Node( 7 ); head.next.next.next = new Node( 40 ); head.next.next.next.next = new Node( 42 ); int result = distanceSum(head); System.out.println(result); } } |
Python3
# Python3 implementation of the approach import sys import math # Structure for a node class Node: def __init__( self , data): self .data = data self . next = None # Function to find the total distance sum def distanceSum(head): # If head is null if not head: return # To store the required sum tsum = 0 temp = head # Traversing through all the nodes one by one while (temp): sq_root = math.sqrt(temp.data) # If current node is not a perfect square # then find left perfect square and # right perfect square if sq_root < temp.data: left_ps = math.floor(sq_root) * * 2 right_ps = math.ceil(sq_root) * * 2 tsum + = (right_ps - left_ps) # Get to the next node temp = temp. next return tsum # Driver code if __name__ = = "__main__" : head = Node( 3 ) head. next = Node( 15 ) head. next . next = Node( 7 ) head. next . next . next = Node( 40 ) head. next . next . next . next = Node( 42 ) result = distanceSum(head) print ( "{}" . format (result)) # This code is contributed by rutvik_56 |
C#
// C# implementation of the approach using System; using System.Collections; using System.Collections.Generic; class GFG { // Structure of a node of linked list class Node { public int data; public Node next; public Node( int data) { this .data = data; this .next = null ; } } // Function to find the total distance sum static int distanceSum(Node head) { // If head is null if (head == null ) return 0; // To store the required sum int tsum = 0; Node temp = head; // Traversing through all the nodes one by one while (temp != null ) { double sq_root = Math.Sqrt(temp.data); // If current node is not a perfect square // then find left perfect square and // right perfect square if (sq_root < temp.data) { int left_ps = ( int )Math.Floor(sq_root) * ( int )Math.Floor(sq_root); int right_ps = ( int )Math.Ceiling(sq_root) * ( int )Math.Ceiling(sq_root); tsum += right_ps - left_ps; } // Get to the next node temp = temp.next; } return tsum; } // Driver code public static void Main( string [] args) { Node head = new Node(3); head.next = new Node(15); head.next.next = new Node(7); head.next.next.next = new Node(40); head.next.next.next.next = new Node(42); int result = distanceSum(head); Console.Write(result); } } // This code is contributed by pratham76 |
41