Dada una lista enlazada, la tarea es encontrar la suma de distancias entre los dos cuadrados perfectos más cercanos para todos los Nodes de la lista enlazada dada.
Ejemplos:
Entrada: 3 -> 15 -> 7 -> NULL
Salida: 15
Para 3: el cuadrado perfecto más cercano a la izquierda es 1 y el más cercano a la derecha 4, es decir, 4-1 = 3
Para 15: 16 – 9 = 7
Para 7: 9 – 4 = 5
3 + 7 + 5 = 15
Entrada: 1 -> 5 -> 10 -> 78 -> 23 -> NULO
Salida: 38
Enfoque: Inicialice sum = 0 y para cada Node, si el valor del Node actual es un cuadrado perfecto en sí mismo, entonces el cuadrado perfecto izquierdo y derecho más cercano será el valor en sí mismo y la distancia será 0. De lo contrario, encuentre los cuadrados perfectos más cercanos izquierdo y derecho. diga PS izquierda y PS derecha y actualice sum = sum + (PS derecha – PS izquierda) .
A continuación se muestra la implementación del enfoque anterior:
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
Javascript
<script>
// JavaScript implementation of the approach
// Structure of a node of linked list
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Function to find the total distance sum
function distanceSum(head) {
// If head is null
if (head == null) return 0;
// To store the required sum
var tsum = 0;
var temp = head;
// Traversing through all the nodes one by one
while (temp != null) {
var 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) {
var left_ps =
parseInt(Math.floor(sq_root)) *
parseInt(Math.floor(sq_root));
var right_ps =
parseInt(Math.ceil(sq_root)) *
parseInt(Math.ceil(sq_root));
tsum += right_ps - left_ps;
}
// Get to the next node
temp = temp.next;
}
return tsum;
}
// Driver code
var 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);
var result = distanceSum(head);
document.write(result);
</script>
Producción:
41
Complejidad de tiempo: O(n)
Publicación traducida automáticamente
Artículo escrito por Vikash Kumar 37 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA