Given a 2-variable polynomial represented by a doubly linked list, the task is to find the partial derivative of a polynomial stored in the doubly-linked list.
Examples:
Input: P(x, y) = 2(x^3 y^4) + 3(x^5 y^7) + 1(x^2 y^6)
Output:
Partial derivatives w.r.t. x: 6(x^2 y^4) + 15(x^4 y^7) + 2(x^1 y^6)
Partial derivatives w.r.t. y: 24(x^2 y^3) + 105(x^4 y^6) + 12(x^1 y^5)
Partial derivatives w.r.t. x and y: 144(x^1 y^2) + 2520(x^3 y^5) + 60(x^0 y^4)Input: P(x, y) = 3(x^2 y^1) + 4(x^2 y^3) + 2(x^4 y^7)
Output:
Partial derivatives w.r.t. x: 6(x^1 y^1) + 8(x^1 y^3) + 8(x^3 y^7)
Partial derivatives w.r.t. y: 6(x^1 y^0) + 24(x^1 y^2) + 56(x^3 y^6)
Partial derivatives w.r.t. x and y: 48(x^0 y^1) + 1008(x^2 y^5)
Approach: Follow the steps below to solve this problem:
- Declare a class or structure to store the contents of a node, i.e. data representing the coefficient, power1 representing the power to which x is raised, power2 representing the power to which y is raised, and the pointers to its next and previous node.
- Declare functions to calculate derivatives with respect to x, derivative with respect to y, and derivative with respect to x and y.
- Calculate and print the derivatives obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Structure of a nodestruct node { node* link1 = NULL; node* link2 = NULL; int data = 0; int pow1 = 0; int pow2 = 0;};// Function to generate Doubly Linked// List from given parametersvoid input_equation(node*& head, int d, int p1, int p2){ node* temp = head; // If list is empty if (head == NULL) { // Create new node node* ptr = new node(); ptr->data = d; ptr->pow1 = p1; ptr->pow2 = p2; // Set it as the head // of the linked list head = ptr; } // If list is not empty else { // Temporarily store // address of the head node temp = head; // Traverse the linked list while (temp->link2 != NULL) { // Link to next node temp = temp->link2; } // Create new node node* ptr = new node(); ptr->data = d; ptr->pow1 = p1; ptr->pow2 = p2; // Connect the nodes ptr->link1 = temp; temp->link2 = ptr; }}// Function to calculate partial// derivative w.r.t. Xvoid derivation_with_x(node*& head){ cout << "Partial derivatives" << " w.r.t. x: "; node* temp = head; // Traverse the Linked List while (temp != NULL) { if (temp->pow1 != 0) { temp->data = (temp->data) * (temp->pow1); temp->pow1 = temp->pow1 - 1; } else { temp->data = 0; temp->pow1 = 0; temp->pow2 = 0; } temp = temp->link2; } temp = head; cout << " " << temp->data << "(x^" << temp->pow1 << " y^" << temp->pow2 << ")"; temp = temp->link2; while (temp != NULL) { cout << " + " << temp->data << "(x^" << temp->pow1 << " y^" << temp->pow2 << ")"; temp = temp->link2; } cout << "\n";}// Function to calculate partial// derivative w.r.t. Yvoid derivation_with_y(node*& head){ cout << "Partial derivatives" << " w.r.t. y: "; node* temp = head; // Traverse the Linked List while (temp != NULL) { if (temp->pow2 != 0) { temp->data = (temp->data) * (temp->pow2); temp->pow2 = temp->pow2 - 1; } else { temp->data = 0; temp->pow1 = 0; temp->pow2 = 0; } temp = temp->link2; } temp = head; cout << " " << temp->data << "(x^" << temp->pow1 << " y^" << temp->pow2 << ")"; temp = temp->link2; while (temp != NULL) { cout << " + " << temp->data << "(x^" << temp->pow1 << " y^" << temp->pow2 << ")"; temp = temp->link2; } cout << "\n";}// Function to calculate partial// derivative w.r.t. XYvoid derivation_with_x_y(node*& head){ cout << "Partial derivatives" << " w.r.t. x and y: "; node* temp = head; // Derivative with respect to // the first variable while (temp != NULL) { if (temp->pow1 != 0) { temp->data = (temp->data) * (temp->pow1); temp->pow1 = temp->pow1 - 1; } else { temp->data = 0; temp->pow1 = 0; temp->pow2 = 0; } temp = temp->link2; } temp = head; // Derivative with respect to // the second variable while (temp != NULL) { if (temp->pow2 != 0) { temp->data = (temp->data) * (temp->pow2); temp->pow2 = temp->pow2 - 1; } else { temp->data = 0; temp->pow1 = 0; temp->pow2 = 0; } temp = temp->link2; } temp = head; cout << " " << temp->data << "(x^" << temp->pow1 << " y^" << temp->pow2 << ")"; temp = temp->link2; // Print the list after the // calculating the derivative while (temp != NULL) { cout << " + " << temp->data << "(x^" << temp->pow1 << " y^" << temp->pow2 << ")"; temp = temp->link2; } cout << "\n";}// Driver Codeint main(){ node* head1 = NULL; // Creating doubly-linked list input_equation(head1, 2, 3, 4); input_equation(head1, 3, 5, 7); input_equation(head1, 1, 2, 6); // Function Call derivation_with_x(head1); derivation_with_y(head1); derivation_with_x_y(head1); return 0;} |
Java
import java.util.*;// Java code// Structure of a nodeclass Node { public int data; public int pow1; public int pow2; public Node link1; public Node link2; public Node(int d, int p1, int p2) { data = d; pow1 = p1; pow2 = p2; link1 = null; link2 = null; }}class GFG { // Function to generate Doubly Linked // List from given parameters public static Node input_equation(Node head, int d, int p1, int p2) { Node temp = head; // If list is empty if (head == null) { // Set it as the head // of the linked list Node ptr = new Node(d, p1, p2); head = ptr; // If list is not empty } else { // Temporarily store // address of the head node temp = head; while (temp.link2 != null) { temp = temp.link2; } Node ptr = new Node(d, p1, p2); // Connect the nodes ptr.link1 = temp; temp.link2 = ptr; } return head; } // Function to calculate partial derivative w.r.t. X public static void derivation_with_x(Node head) { String tem = "Partial derivatives w.r.t. x: "; Node temp = head; while (temp != null) { if (temp.pow1 != 0) { temp.data = (temp.data) * (temp.pow1); temp.pow1 = temp.pow1 - 1; } else { temp.data = 0; temp.pow1 = 0; temp.pow2 = 0; } temp = temp.link2; } temp = head; if (temp.data != 0) { tem = tem + " " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; while (temp != null) { if (temp.data != 0) { tem = tem + " + " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; } System.out.println(tem); } // Function to calculate partial // derivative w.r.t. Y public static void derivation_with_y(Node head) { String tem = "Partial derivatives w.r.t. y: "; Node temp = head; while (temp != null) { if (temp.pow2 != 0) { temp.data = (temp.data) * (temp.pow2); temp.pow2 = temp.pow2 - 1; } else { temp.data = 0; temp.pow1 = 0; temp.pow2 = 0; } temp = temp.link2; } temp = head; if (temp.data != 0) { tem = tem + " " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; while (temp != null) { if (temp.data != 0) { tem = tem + " + " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; } System.out.println(tem); } // Function to calculate partial // derivative w.r.t. XY public static void derivation_with_x_y(Node head) { String tem = "Partial derivatives w.r.t. xy: "; Node temp = head; while (temp != null) { if (temp.pow1 != 0 && temp.pow2 != 0) { temp.data = (temp.data) * (temp.pow1) * (temp.pow2); temp.pow1 = temp.pow1 - 1; temp.pow2 = temp.pow2 - 1; } else { temp.data = 0; temp.pow1 = 0; temp.pow2 = 0; } temp = temp.link2; } temp = head; if (temp.data != 0) { tem = tem + " " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; while (temp != null) { if (temp.data != 0) { tem = tem + " + " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; } System.out.println(tem); } public static void main(String[] args) { // Creating doubly-linked list Node head = null; head = input_equation(head, 2, 3, 4); head = input_equation(head, 3, 5, 7); head = input_equation(head, 1, 2, 6); // Function Call derivation_with_x(head); derivation_with_y(head); derivation_with_x_y(head); }}// The code is contributed by phasing17 |
Python3
# Python code for the above approach# Structure of a nodeclass Node: def __init__(self, data, p1, p2): self.data = data self.pow1 = p1 self.pow2 = p2 self.link1 = None self.link2 = None # Function to generate Doubly Linked# List from given parametersdef input_equation(head, d, p1, p2): temp = head # If list is empty if head is None: # Set it as the head # of the linked list ptr = Node(d,p1,p2) head = ptr #If list is not empty else: # Temporarily store # address of the head node temp = head while temp.link2 is not None: temp = temp.link2 ptr = Node(d,p1,p2) # Connect the nodes ptr.link1 = temp temp.link2 = ptr return head# Function to calculate partial derivative w.r.t. Xdef derivation_with_x(head): print("Partial derivatives w.r.t. x: ", end = "") temp = head while temp is not None: if temp.pow1 != 0: temp.data = (temp.data) * (temp.pow1) temp.pow1 = temp.pow1 - 1 else: temp.data = 0 temp.pow1 = 0 temp.pow2 = 0 temp = temp.link2 temp = head if temp.data != 0: print(" " + str(temp.data) + "(x^" + str(temp.pow1) + " y^" + str(temp.pow2) + ")", end = "") temp = temp.link2 while temp is not None: if temp.data != 0: print(" + " + str(temp.data) + "(x^" + str(temp.pow1) + " y^" + str(temp.pow2) + ")", end = "") temp = temp.link2 print() # Function to calculate partial# derivative w.r.t. Ydef derivation_with_y(head): print("Partial derivatives w.r.t. y: ", end = "") temp = head while temp is not None: if temp.pow2 != 0: temp.data = (temp.data) * (temp.pow2) temp.pow2 = temp.pow2 - 1 else: temp.data = 0 temp.pow1 = 0 temp.pow2 = 0 temp = temp.link2 temp = head if temp.data != 0: print(" " + str(temp.data) + "(x^" + str(temp.pow1) + " y^" + str(temp.pow2) + ")", end = "") temp = temp.link2 while temp is not None: if temp.data != 0: print(" + " + str(temp.data) + "(x^" + str(temp.pow1) + " y^" + str(temp.pow2) + ")", end = "") temp = temp.link2 print() #Function to calculate partial# derivative w.r.t. XYdef derivation_with_x_y(head): print("Partial derivatives w.r.t. xy: ", end = "") temp = head while temp is not None: if temp.pow1 != 0 and temp.pow2 != 0: temp.data = (temp.data) * (temp.pow1) * (temp.pow2) temp.pow1 = temp.pow1 - 1 temp.pow2 = temp.pow2 - 1 else: temp.data = 0 temp.pow1 = 0 temp.pow2 = 0 temp = temp.link2 temp = head if temp.data != 0: print(" " + str(temp.data) + "(x^" + str(temp.pow1) + " y^" + str(temp.pow2) + ")", end = "") temp = temp.link2 while temp is not None: if temp.data != 0: print(" + " + str(temp.data) + "(x^" + str(temp.pow1) + " y^" + str(temp.pow2) + ")", end = "") temp = temp.link2 print() # Driver Codeif __name__ == "__main__": #Creating doubly-linked list head = None head = input_equation(head, 2,3,4) head = input_equation(head, 3,5,7) head = input_equation(head, 1,2,6) #Function Call derivation_with_x(head) derivation_with_y(head) derivation_with_x_y(head)# This code is contributed by lokeshpotta20. |
C#
using System;using System.Collections;using System.Collections.Generic;using System.Linq;// C# code// Structure of a nodeclass Node { public int data; public int pow1; public int pow2; public Node link1; public Node link2; public Node(int d,int p1,int p2) { data = d; pow1 = p1; pow2 = p2; link1 = null; link2 = null; }}class HelloWorld { // Function to generate Doubly Linked // List from given parameters public static Node input_equation(Node head,int d,int p1,int p2) { Node temp = head; // If list is empty if (head == null) { // Set it as the head // of the linked list Node ptr = new Node(d,p1,p2); head = ptr; //If list is not empty } else { // Temporarily store // address of the head node temp = head; while (temp.link2 != null) { temp = temp.link2; } Node ptr = new Node(d,p1,p2); // Connect the nodes ptr.link1 = temp; temp.link2 = ptr; } return head; } // Function to calculate partial derivative w.r.t. X public static void derivation_with_x(Node head) { string tem = "Partial derivatives w.r.t. x: "; Node temp = head; while (temp != null) { if (temp.pow1 != 0) { temp.data = (temp.data) * (temp.pow1); temp.pow1 = temp.pow1 - 1; } else { temp.data = 0; temp.pow1 = 0; temp.pow2 = 0; } temp = temp.link2; } temp = head; if (temp.data != 0) { tem = tem + " " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; while (temp != null) { if (temp.data != 0) { tem = tem +" + " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; } Console.WriteLine(tem); } // Function to calculate partial // derivative w.r.t. Y public static void derivation_with_y(Node head) { string tem = "Partial derivatives w.r.t. y: "; Node temp = head; while (temp != null) { if (temp.pow2 != 0) { temp.data = (temp.data) * (temp.pow2); temp.pow2 = temp.pow2 - 1; } else { temp.data = 0; temp.pow1 = 0; temp.pow2 = 0; } temp = temp.link2; } temp = head; if (temp.data != 0) { tem = tem + " " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; while (temp != null) { if (temp.data != 0) { tem = tem + " + " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; } Console.WriteLine(tem); } // Function to calculate partial // derivative w.r.t. XY public static void derivation_with_x_y(Node head) { string tem = "Partial derivatives w.r.t. xy: "; Node temp = head; while (temp != null) { if (temp.pow1 != 0 && temp.pow2 != 0) { temp.data = (temp.data) * (temp.pow1) * (temp.pow2); temp.pow1 = temp.pow1 - 1; temp.pow2 = temp.pow2 - 1; } else { temp.data = 0; temp.pow1 = 0; temp.pow2 = 0; } temp = temp.link2; } temp = head; if (temp.data != 0) { tem = tem + " " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; while (temp != null) { if (temp.data != 0) { tem = tem + " + " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; } Console.WriteLine(tem); } static void Main() { // Creating doubly-linked list Node head = null; head = input_equation(head, 2,3,4); head = input_equation(head, 3,5,7); head = input_equation(head, 1,2,6); //Function Call derivation_with_x(head); derivation_with_y(head); derivation_with_x_y(head); }}// The code is contributed by Nidhi goel. |
Javascript
// Javascript code// Structure of a nodeclass Node { constructor(data, p1, p2) { this.data = data; this.pow1 = p1; this.pow2 = p2; this.link1 = null; this.link2 = null; }}// Function to generate Doubly Linked// List from given parametersfunction input_equation(head, d, p1, p2) { let temp = head; // If list is empty if (head == null) { // Set it as the head // of the linked list let ptr = new Node(d,p1,p2); head = ptr; //If list is not empty } else { // Temporarily store // address of the head node temp = head; while (temp.link2 != null) { temp = temp.link2; } let ptr = new Node(d,p1,p2); // Connect the nodes ptr.link1 = temp; temp.link2 = ptr; } return head;}// Function to calculate partial derivative w.r.t. Xfunction derivation_with_x(head) { tem = "Partial derivatives w.r.t. x: "; let temp = head; while (temp != null) { if (temp.pow1 != 0) { temp.data = (temp.data) * (temp.pow1); temp.pow1 = temp.pow1 - 1; } else { temp.data = 0; temp.pow1 = 0; temp.pow2 = 0; } temp = temp.link2; } temp = head; if (temp.data != 0) { tem = tem + " " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; while (temp != null) { if (temp.data != 0) { tem = tem +" + " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; } console.log(tem);} // Function to calculate partial// derivative w.r.t. Yfunction derivation_with_y(head) { tem = "Partial derivatives w.r.t. y: "; let temp = head; while (temp != null) { if (temp.pow2 != 0) { temp.data = (temp.data) * (temp.pow2); temp.pow2 = temp.pow2 - 1; } else { temp.data = 0; temp.pow1 = 0; temp.pow2 = 0; } temp = temp.link2; } temp = head; if (temp.data != 0) { tem = tem + " " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; while (temp != null) { if (temp.data != 0) { tem = tem + " + " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; } console.log(tem);} // Function to calculate partial// derivative w.r.t. XYfunction derivation_with_x_y(head) { tem = "Partial derivatives w.r.t. xy: "; let temp = head; while (temp != null) { if (temp.pow1 != 0 && temp.pow2 != 0) { temp.data = (temp.data) * (temp.pow1) * (temp.pow2); temp.pow1 = temp.pow1 - 1; temp.pow2 = temp.pow2 - 1; } else { temp.data = 0; temp.pow1 = 0; temp.pow2 = 0; } temp = temp.link2; } temp = head; if (temp.data != 0) { tem = tem + " " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; while (temp != null) { if (temp.data != 0) { tem = tem + " + " + temp.data + "(x^" + temp.pow1 + " y^" + temp.pow2 + ")"; } temp = temp.link2; } console.log(tem);} // Driver Codefunction main() { // Creating doubly-linked list let head = null; head = input_equation(head, 2,3,4); head = input_equation(head, 3,5,7); head = input_equation(head, 1,2,6); //Function Call derivation_with_x(head); derivation_with_y(head); derivation_with_x_y(head);}main(); |
Output:
Partial derivatives w.r.t. x: 6(x^2 y^4) + 15(x^4 y^7) + 2(x^1 y^6) Partial derivatives w.r.t. y: 24(x^2 y^3) + 105(x^4 y^6) + 12(x^1 y^5) Partial derivatives w.r.t. x and y: 144(x^1 y^2) + 2520(x^3 y^5) + 60(x^0 y^4)
Time Complexity: O(N)
Auxiliary Space: O(1)
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!