Given an Linked list containing N positive integer, the task is to find the sum of all the perfect numbers from the list.
A number is perfect if is equal to the sum of its proper divisors i.e. the sum of its positive divisors excluding the number itself.
Examples:
Input: L1 = 3 -> 6 -> 9
Output:6
Proper divisor sum of 3 = 1
ans=0
Proper divisor sum of 6 = 1 + 2 + 3 = 6
ans=6;
Proper divisor sum of 9 = 1 + 3 = 4
ans=6;
Input: L1 = 17 -> 6 -> 10 -> 6 -> 4
Output: 12
Approach: Initialise sum = 0 and for every node of the list, find the sum of its proper divisors say sumFactors. If cur_node = sumFactors then update the resultant sum as sum = sum + cur_node. Print the sum in the end.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Node of the singly linked liststruct Node { int data; Node* next;};// Function to insert a node// at the beginning of// the singly Linked Listvoid 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 of 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 nint 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 sumint 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 codeint 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 approachclass GFG{// Node of the singly linked liststatic class Node { int data; Node next;};// Function to insert a node// at the beginning of// the singly Linked Liststatic 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 of 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 nstatic 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 sumstatic 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 codepublic 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 Classclass 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 Codeif __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 approachusing System;class GFG{// Node of the singly linked listclass Node { public int data; public Node next;};// Function to insert a node// at the beginning of// the singly Linked Liststatic 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 of 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 nstatic 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 sumstatic 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 codepublic 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 of 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> |
Output:
12
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
