Dada una lista enlazada circular simple. La tarea es encontrar la suma y el producto de los Nodes que son divisibles por K de la lista enlazada dada.
Ejemplos :
Input : List = 5->6->7->8->9->10->11->11
K = 11
Output : Sum = 22, Product = 121
Input : List = 15->7->3->9->11->5
K = 5
Output : Product = 75, Sum = 20
Suma y producto del Node de lista enlazada circular única
Acercarse:
- Inicialice un puntero actual con el encabezado de la lista circular enlazada y una suma variable suma con 0 y una variable producto producto con 1.
- Comience a recorrer la lista enlazada utilizando un bucle do-while hasta que se atraviesen todos los Nodes.
- Si los datos del Node actual son divisibles por la clave dada.
- Agregue el valor del Node actual a la suma, es decir, sum = sum + current -> data .
- Multiplique el valor del Node actual por el producto, es decir, producto = producto * actual -> datos .
- Incremente el puntero al siguiente Node de la lista enlazada, es decir, temp = temp -> next .
- Imprime la suma y el producto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to calculate sum and product from
// singly circular linked list nodes
// which are divisible by given key
#include <bits/stdc++.h>
using namespace std;
// Circular list node
struct Node {
int data;
struct Node* next;
};
// Function to calculate sum and product
void sumProduct(struct Node* head, int key)
{
struct Node* current = head;
int sum = 0, product = 1;
// if list is empty simply show message
if (head == NULL) {
printf("\nDisplay List is empty\n");
return;
}
// traverse first to last node
else {
do {
// check if current node's data is
// divisible by key
if ((current->data) % key == 0) {
// Calculate sum
sum += current->data;
// Calculate product
product *= current->data;
}
current = current->next;
} while (current != head);
}
cout << "Sum = " << sum << ", Product = " << product;
}
// Function print the list
void displayList(struct Node* head)
{
struct Node* current = head;
// if list is empty simply show message
if (head == NULL) {
printf("\nDisplay List is empty\n");
return;
}
// traverse first to last node
else {
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);
}
}
// Function to insert a node at the end of
// a Circular linked list
void InsertNode(struct Node** head, int data)
{
struct Node* current = *head;
// Create a new node
struct Node* newNode = new Node;
// check node is created or not
if (!newNode) {
printf("\nMemory Error\n");
return;
}
// insert data into newly created node
newNode->data = data;
// check list is empty
// if not have any node then
// make first node it
if (*head == NULL) {
newNode->next = newNode;
*head = newNode;
return;
}
// if list have already some node
else {
// move first node to last node
while (current->next != *head) {
current = current->next;
}
// put first or head node address in new node link
newNode->next = *head;
// put new node address into last node link(next)
current->next = newNode;
}
}
// Driver Code
int main()
{
struct Node* head = NULL;
InsertNode(&head, 5);
InsertNode(&head, 6);
InsertNode(&head, 7);
InsertNode(&head, 8);
InsertNode(&head, 9);
InsertNode(&head, 10);
InsertNode(&head, 11);
InsertNode(&head, 11);
cout << "Initial List: ";
displayList(head);
cout << endl;
sumProduct(head, 11);
return 0;
}
Java
// Java program to calculate sum and product from
// singly circular linked list nodes
// which are divisible by given key
import java.util.*;
class Solution
{
// Circular list node
static class Node {
int data;
Node next;
}
// Function to calculate sum and product
static void sumProduct( Node head, int key)
{
Node current = head;
int sum = 0, product = 1;
// if list is empty simply show message
if (head == null) {
System.out.print("\nDisplay List is empty\n");
return;
}
// traverse first to last node
else {
do {
// check if current node's data is
// divisible by key
if ((current.data) % key == 0) {
// Calculate sum
sum += current.data;
// Calculate product
product *= current.data;
}
current = current.next;
} while (current != head);
}
System.out.print( "Sum = " + sum + ", Product = " + product);
}
// Function print the list
static void displayList( Node head)
{
Node current = head;
// if list is empty simply show message
if (head == null) {
System.out.print("\nDisplay List is empty\n");
return;
}
// traverse first to last node
else {
do {
System.out.print( current.data+" ");
current = current.next;
} while (current != head);
}
}
// Function to insert a node at the end of
// a Circular linked list
static Node InsertNode( Node head, int data)
{
Node current = head;
// Create a new node
Node newNode = new Node();
// check node is created or not
if (newNode==null) {
System.out.print("\nMemory Error\n");
return head;
}
// insert data into newly created node
newNode.data = data;
// check list is empty
// if not have any node then
// make first node it
if (head == null) {
newNode.next = newNode;
head = newNode;
return head;
}
// if list have already some node
else {
// move first node to last node
while (current.next != head) {
current = current.next;
}
// put first or head node address in new node link
newNode.next = head;
// put new node address into last node link(next)
current.next = newNode;
}
return head;
}
// Driver Code
public static void main(String args[])
{
Node head=null ;
head =InsertNode(head, 5);
head =InsertNode(head, 6);
head =InsertNode(head, 7);
head =InsertNode(head, 8);
head =InsertNode(head, 9);
head =InsertNode(head, 10);
head =InsertNode(head, 11);
head =InsertNode(head, 11);
System.out.print( "Initial List: ");
displayList(head);
System.out.println();
sumProduct(head, 11);
}
}
//contributed by Arnab Kundu
Python3
# Python3 program to calculate sum and
# product from singly circular linked list
# nodes which are divisible by given key
import math
# Circular list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to calculate sum and product
def sumProduct(head, key):
current = head
sum = 0
product = 1
# if list is empty simply show message
if (head == None):
print("\nDisplay List is empty\n")
return
# traverse first to last node
else :
# check if current node's data is
# divisible by key
if ((current.data) % key == 0) :
# Calculate sum
sum = sum + current.data
# Calculate product
product = product * current.data
current = current.next
while (current != head):
if ((current.data) % key == 0) :
# Calculate sum
sum = sum + current.data
# Calculate product
product = product * current.data
current = current.next
print("\nSum =", sum, end = ", ")
print("Product =", product)
# Function print the list
def displayList(head):
current = head
# if list is empty simply show message
if (head == None):
print("\nDisplay List is empty\n")
return
# traverse first to last node
else :
print(current.data, end = " ")
current = current.next
while (current != head):
print(current.data, end = " ")
current = current.next
# Function to insert a node at the end of
# a Circular linked list
def InsertNode(head, data):
current = head
# Create a new node
newNode = Node(data)
# check node is created or not
if (newNode == None):
print("\nMemory Error\n")
return head
# insert data o newly created node
newNode.data = data
# check list is empty
# if not have any node then
# make first node it
if (head == None):
newNode.next = newNode
head = newNode
return head
# if list have already some node
else :
# move first node to last node
while (current.next != head):
current = current.next
# put first or head node address
# in new node link
newNode.next = head
# put new node address o last node link(next)
current.next = newNode
return head
# Driver Code
if __name__=='__main__':
head = None
head = InsertNode(head, 5)
head = InsertNode(head, 6)
head = InsertNode(head, 7)
head = InsertNode(head, 8)
head = InsertNode(head, 9)
head = InsertNode(head, 10)
head = InsertNode(head, 11)
head = InsertNode(head, 11)
print("Initial List: ", end = "")
displayList(head)
sumProduct(head, 11)
# This code is contributed by Srathore
C#
// C# program to calculate sum and product from
// singly circular linked list nodes
// which are divisible by given key
using System;
class GFG
{
// Circular list node
class Node
{
public int data;
public Node next;
}
// Function to calculate sum and product
static void sumProduct( Node head, int key)
{
Node current = head;
int sum = 0, product = 1;
// if list is empty simply show message
if (head == null)
{
Console.Write("\nDisplay List is empty\n");
return;
}
// traverse first to last node
else
{
do
{
// check if current node's data is
// divisible by key
if ((current.data) % key == 0)
{
// Calculate sum
sum += current.data;
// Calculate product
product = current.data;
}
current = current.next;
} while (current != head);
}
Console.Write( "Sum = " + sum + ", Product = " + product);
}
// Function print the list
static void displayList( Node head)
{
Node current = head;
// if list is empty simply show message
if (head == null)
{
Console.Write("\nDisplay List is empty\n");
return;
}
// traverse first to last node
else
{
do
{
Console.Write( current.data+" ");
current = current.next;
} while (current != head);
}
}
// Function to insert a node at the end of
// a Circular linked list
static Node InsertNode( Node head, int data)
{
Node current = head;
// Create a new node
Node newNode = new Node();
// check node is created or not
if (newNode==null)
{
Console.Write("\nMemory Error\n");
return head;
}
// insert data into newly created node
newNode.data = data;
// check list is empty
// if not have any node then
// make first node it
if (head == null)
{
newNode.next = newNode;
head = newNode;
return head;
}
// if list have already some node
else
{
// move first node to last node
while (current.next != head)
{
current = current.next;
}
// put first or head node address in new node link
newNode.next = head;
// put new node address into last node link(next)
current.next = newNode;
}
return head;
}
// Driver Code
public static void Main()
{
Node head=null ;
head =InsertNode(head, 5);
head =InsertNode(head, 6);
head =InsertNode(head, 7);
head =InsertNode(head, 8);
head =InsertNode(head, 9);
head =InsertNode(head, 10);
head =InsertNode(head, 11);
head =InsertNode(head, 11);
Console.Write( "Initial List: ");
displayList(head);
Console.WriteLine();
sumProduct(head, 11);
}
}
// This code has been contributed
// by PrinciRaj1992
Javascript
<script>
// JavaScript program to calculate
// sum and product from
// singly circular linked list nodes
// which are divisible by given key
// Circular list node
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Function to calculate sum and product
function sumProduct(head , key) {
var current = head;
var sum = 0, product = 1;
// if list is empty simply show message
if (head == null) {
document.write("\nDisplay List is empty\n");
return;
}
// traverse first to last node
else {
do {
// check if current node's data is
// divisible by key
if ((current.data) % key == 0) {
// Calculate sum
sum += current.data;
// Calculate product
product *= current.data;
}
current = current.next;
} while (current != head);
}
document.write("Sum = " + sum + ", Product = " +
product);
}
// Function print the list
function displayList(head) {
var current = head;
// if list is empty simply show message
if (head == null) {
document.write("\nDisplay List is empty\n");
return;
}
// traverse first to last node
else {
do {
document.write(current.data + " ");
current = current.next;
} while (current != head);
}
}
// Function to insert a node at the end of
// a Circular linked list
function InsertNode(head , data) {
var current = head;
// Create a new node
var newNode = new Node();
// check node is created or not
if (newNode == null) {
document.write("\nMemory Error\n");
return head;
}
// insert data into newly created node
newNode.data = data;
// check list is empty
// if not have any node then
// make first node it
if (head == null) {
newNode.next = newNode;
head = newNode;
return head;
}
// if list have already some node
else {
// move first node to last node
while (current.next != head) {
current = current.next;
}
// put first or head node
// address in new node link
newNode.next = head;
// put new node address into
// last node link(next)
current.next = newNode;
}
return head;
}
// Driver Code
var head = null;
head = InsertNode(head, 5);
head = InsertNode(head, 6);
head = InsertNode(head, 7);
head = InsertNode(head, 8);
head = InsertNode(head, 9);
head = InsertNode(head, 10);
head = InsertNode(head, 11);
head = InsertNode(head, 11);
document.write("Initial List: ");
displayList(head);
document.write("<br/>");
sumProduct(head, 11);
// This code is contributed by todaysgaurav
</script>
Producción:
Initial List: 5 6 7 8 9 10 11 11 Sum = 22, Product = 121
Complejidad de tiempo: O (n), ya que estamos usando un bucle para atravesar n veces. Donde n es el número de Nodes en la lista enlazada.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.