Dada una lista enlazada que contiene N enteros positivos, la tarea es encontrar la suma de todos los números perfectos de la lista.
Un número es perfecto si es igual a la suma de sus divisores propios, es decir, la suma de sus divisores positivos excluyendo el propio número.
Ejemplos:
Entrada: L1 = 3 -> 6 -> 9
Salida: 6
Divisor propio suma de 3 = 1
ans=0
Divisor propio suma de 6 = 1 + 2 + 3 = 6
ans=6;
Divisor propio suma de 9 = 1 + 3 = 4
ans=6;
Entrada: L1 = 17 -> 6 -> 10 -> 6 -> 4
Salida: 12
Enfoque: Inicialice sum = 0 y para cada Node de la lista, encuentre la suma de sus divisores propios, digamos sumFactors . Si cur_node = sumFactors , actualice la suma resultante como sum = sum + cur_node . Imprime la suma al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Node of the singly linked list
struct Node {
int data;
Node* next;
};
// Function to insert a node
// at the beginning of
// the singly Linked List
void push(Node** head_ref, int new_data)
{
// allocate node
Node* new_node
= (Node*)malloc(
sizeof(struct Node));
// put in the data
new_node->data = new_data;
// link the old list off the new node
new_node->next = (*head_ref);
// move the head to point
// to the new node
(*head_ref) = new_node;
}
// Function to return the sum of
// all the proper factors of n
int sumOfFactors(int n)
{
int sum = 0;
for (int f = 1; f <= n / 2; f++) {
// f is the factor of n
if (n % f == 0) {
sum += f;
}
}
return sum;
}
// Function to return the required sum
int getSum(Node* head_1)
{
// To store the sum
int sum = 0;
Node* ptr = head_1;
while (ptr != NULL) {
// If current element is non-zero
// and equal to the sum
// of proper factors of itself
if (ptr->data > 0
&& ptr->data
== sumOfFactors(ptr->data)) {
sum += ptr->data;
}
ptr = ptr->next;
}
return sum;
}
// Driver code
int main()
{
// start with the empty list
Node* head1 = NULL;
// create the linked list
push(&head1, 17);
push(&head1, 6);
push(&head1, 10);
push(&head1, 6);
push(&head1, 4);
int k = getSum(head1);
cout << k;
return 0;
}
Java
// Java implementation of the approach
class GFG{
// Node of the singly linked list
static class Node
{
int data;
Node next;
};
// Function to insert a node
// at the beginning of
// the singly Linked List
static Node push(Node head_ref,
int new_data)
{
// Allocate node
Node new_node= new Node();
// Put in the data
new_node.data = new_data;
// Link the old list off the new node
new_node.next = head_ref;
// Move the head to point
// to the new node
head_ref = new_node;
return head_ref;
}
// Function to return the sum of
// all the proper factors of n
static int sumOfFactors(int n)
{
int sum = 0;
for(int f = 1; f <= n / 2; f++)
{
// f is the factor of n
if (n % f == 0)
{
sum += f;
}
}
return sum;
}
// Function to return the required sum
static int getSum(Node head_1)
{
// To store the sum
int sum = 0;
Node ptr = head_1;
while (ptr != null)
{
// If current element is non-zero
// and equal to the sum of proper
// factors of itself
if (ptr.data > 0 && ptr.data ==
sumOfFactors(ptr.data))
{
sum += ptr.data;
}
ptr = ptr.next;
}
return sum;
}
// Driver code
public static void main(String[] args)
{
// Start with the empty list
Node head = new Node();
// Create the linked list
head = push(head, 17);
head = push(head, 6);
head = push(head, 10);
head = push(head, 6);
head = push(head, 4);
int k = getSum(head);
System.out.print(k);
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 implementation of the approach # Node class class Node: # Function to initialize the node object def __init__(self, data): self.data = data self.next = None # Linked List Class class LinkedList: # Function to initialize the # LinkedList class. def __init__(self): self.head = None # This function insert a new node at # the beginning of the linked list def push(self, new_data): # Create a new Node new_node = Node(new_data) # Make next of new Node as head new_node.next = self.head # Move the head to point to new Node self.head = new_node # Function to return the required sum def getSum(self): # To store the sum Sum = 0 # Initialising the pointer ptr = self.head while(True): # If current element is non Zero # and is a perfect number then # add to sum if(ptr.data > 0 and ptr.data == sumOfFactors(ptr.data)): Sum += ptr.data # Breaking the loop if list terminates if(ptr.next == None): break # Moving to next node ptr = ptr.next # Returning the sum return Sum # Function to return the sum of # all the proper factors of n def sumOfFactors(n): Sum = 0 # f is factor of n for f in range(1, (n // 2) + 1): if(n % f == 0): Sum += f return Sum # Driver Code if __name__=='__main__': # Start with empty list head1 = LinkedList() # Create the linked list head1.push(17) head1.push(6) head1.push(10) head1.push(6) head1.push(4) # Getting the required sum k = head1.getSum() print(k) # This code is contributed by Amit Mangal
C#
// C# implementation of the approach
using System;
class GFG{
// Node of the singly linked list
class Node
{
public int data;
public Node next;
};
// Function to insert a node
// at the beginning of
// the singly Linked List
static Node push(Node head_ref,
int new_data)
{
// Allocate node
Node new_node= new Node();
// Put in the data
new_node.data = new_data;
// Link the old list off the new node
new_node.next = head_ref;
// Move the head to point
// to the new node
head_ref = new_node;
return head_ref;
}
// Function to return the sum of
// all the proper factors of n
static int sumOfFactors(int n)
{
int sum = 0;
for(int f = 1; f <= n / 2; f++)
{
// f is the factor of n
if (n % f == 0)
{
sum += f;
}
}
return sum;
}
// Function to return the required sum
static int getSum(Node head_1)
{
// To store the sum
int sum = 0;
Node ptr = head_1;
while (ptr != null)
{
// If current element is non-zero
// and equal to the sum of proper
// factors of itself
if (ptr.data > 0 && ptr.data ==
sumOfFactors(ptr.data))
{
sum += ptr.data;
}
ptr = ptr.next;
}
return sum;
}
// Driver code
public static void Main(String[] args)
{
// Start with the empty list
Node head = new Node();
// Create the linked list
head = push(head, 17);
head = push(head, 6);
head = push(head, 10);
head = push(head, 6);
head = push(head, 4);
int k = getSum(head);
Console.Write(k);
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// JavaScript implementation of the approach
// Node of the singly linked list
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Function to insert a node
// at the beginning of
// the singly Linked List
function push(head_ref, new_data) {
// Allocate node
var new_node = new Node();
// Put in the data
new_node.data = new_data;
// Link the old list off the new node
new_node.next = head_ref;
// Move the head to point
// to the new node
head_ref = new_node;
return head_ref;
}
// Function to return the sum of
// all the proper factors of n
function sumOfFactors(n) {
var sum = 0;
for (var f = 1; f <= parseInt(n / 2); f++) {
// f is the factor of n
if (n % f == 0) {
sum += f;
}
}
return sum;
}
// Function to return the required sum
function getSum(head_1) {
// To store the sum
var sum = 0;
var ptr = head_1;
while (ptr != null) {
// If current element is non-zero
// and equal to the sum of proper
// factors of itself
if (ptr.data > 0 && ptr.data == sumOfFactors(ptr.data)) {
sum += ptr.data;
}
ptr = ptr.next;
}
return sum;
}
// Driver code
// Start with the empty list
var head = new Node();
// Create the linked list
head = push(head, 17);
head = push(head, 6);
head = push(head, 10);
head = push(head, 6);
head = push(head, 4);
var k = getSum(head);
document.write(k);
// This code is contributed by rdtank.
</script>
Producción:
12
Publicación traducida automáticamente
Artículo escrito por ShivaTeja2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA