Given a singly linked list, the task is to replace every node with its closest bell number.
Bell numbers are a sequence of numbers that represent the number of partitions of a set. In other words, given a set of n elements, the Bell number for n represents the total number of distinct ways that the set can be partitioned into subsets.
The first few Bell numbers are 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, …
Examples:
Input: 14 -> 7 -> 190 -> 2 -> 5 -> NULL
Output: 15 -> 5 -> 203 -> 2 -> 5 -> NULL
Explanation: The closest Bell numbers for each node are:
- Node 1 (value = 14): Closest Bell number = 15.
- Node 2 (value = 7): Closest Bell number = 5.
- Node 3 (value = 190): Closest Bell number = 203.
- Node 4 (value = 2): Closest Bell number = 2.
- Node 5 (value = 5): Closest Bell number = 5.
Input: 50 -> 1 -> 4 -> NULL
Output: 52 -> 1 -> 5 -> NULL
Explanation: The closest Bell numbers for each node are:
- Node 1 (value = 50): Closest Bell number = 52.
- Node 1 (value = 1): Closest Bell number = 1.
- Node 1 (value = 4): Closest Bell number = 5.
Approach: This can be solved with the following idea:
The algorithm first calculates the Bell number at a given index by filling a 2D array using a dynamic programming approach. Then, it finds the closest Bell number to a given node value by iterating through the Bell numbers until it finds a Bell number greater than or equal to the node value. It then compares the difference between the previous and current Bell numbers to determine which one is closer to the node value. Finally, it replaces each node in the linked list with its closest Bell number using a while loop that iterates through each node in the linked list.
Steps of the above approach:
- Define a bellNumber function that takes an integer n as an argument and returns the nth Bell number. The function uses dynamic programming to calculate the Bell number.
- Define a closestBell function that takes an integer n as an argument and returns the closest Bell number to n.
- This function iteratively calls the bellNumber function until it finds the smallest Bell number greater than or equal to n.
- If n is less than the first Bell number (which is 1), then the function returns the first Bell number. Otherwise, the function compares the difference between n and the previous Bell number to the difference between the next Bell number and n and returns the closer Bell number.
- Define a replaceWithBell function that takes the head of a linked list as an argument and replaces the data value of each node in the list with the closest Bell number to its original data value.
- The function iterates through each node in the list, calls the closestBell function to find the closest Bell number to the node’s original data value, and assigns that value to the node’s data field.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <cmath>#include <iostream>using namespace std;// Node structure of singly linked liststruct Node { int data; Node* next;};// Function to add a new node at the// beginning of the linked listvoid push(Node** head_ref, int new_data){ Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node;}// Function to print the linked listvoid printList(Node* node){ while (node != NULL) { cout << node->data; if (node->next != NULL) { cout << " -> "; } node = node->next; }}// Function to find the Bell number at// the given indexint bellNumber(int n){ int bell[n + 1][n + 1]; bell[0][0] = 1; for (int i = 1; i <= n; i++) { bell[i][0] = bell[i - 1][i - 1]; for (int j = 1; j <= i; j++) { bell[i][j] = bell[i - 1][j - 1] + bell[i][j - 1]; } } return bell[n][0];}// Function to find the closest Bell number// to a given node valueint closestBell(int n){ int bellNum = 0; while (bellNumber(bellNum) < n) { bellNum++; } if (bellNum == 0) { return bellNumber(bellNum); } else { int prev = bellNumber(bellNum - 1); int curr = bellNumber(bellNum); return (n - prev < curr - n) ? prev : curr; }}// Function to replace every node with// its closest Bell numbervoid replaceWithBell(Node* node){ while (node != NULL) { node->data = closestBell(node->data); node = node->next; }}// Driver codeint main(){ Node* head = NULL; // Creating the linked list push(&head, 5); push(&head, 2); push(&head, 190); push(&head, 7); push(&head, 14); // Function call replaceWithBell(head); printList(head); return 0;} |
Java
// Java code for the above approachclass GFG { // Node structure of singly linked list static class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } // Function to add a new node at the // beginning of the linked list static void push(Node[] head_ref, int newData) { Node newNode = new Node(newData); newNode.next = head_ref[0]; head_ref[0] = newNode; } // Function to print the linked list static void printList(Node node) { while (node != null) { System.out.print(node.data); if (node.next != null) { System.out.print(" -> "); } node = node.next; } } // Function to find the Bell number at // the given index static int bellNumber(int n) { int[][] bell = new int[n + 1][n + 1]; bell[0][0] = 1; for (int i = 1; i <= n; i++) { bell[i][0] = bell[i - 1][i - 1]; for (int j = 1; j <= i; j++) { bell[i][j] = bell[i - 1][j - 1] + bell[i][j - 1]; } } return bell[n][0]; } // Function to find the closest Bell number // to a given node value static int closestBell(int n) { int bellNum = 0; while (bellNumber(bellNum) < n) { bellNum++; } if (bellNum == 0) { return bellNumber(bellNum); } else { int prev = bellNumber(bellNum - 1); int curr = bellNumber(bellNum); return (n - prev < curr - n) ? prev : curr; } } // Function to replace every node with // its closest Bell number static void replaceWithBell(Node node) { while (node != null) { node.data = closestBell(node.data); node = node.next; } } // Driver code public static void main(String[] args) { Node[] head = new Node[1]; // Creating the linked list push(head, 5); push(head, 2); push(head, 190); push(head, 7); push(head, 14); // Function call replaceWithBell(head[0]); printList(head[0]); }}// This code is contributed by shivamgupta310570 |
Python3
import math# Node class for singly linked listclass Node: def __init__(self, data): self.data = data self.next = None# Function to add a new node at the beginning of the linked listdef push(head_ref, new_data): new_node = Node(new_data) new_node.next = head_ref head_ref = new_node return head_ref# Function to print the linked listdef printList(node): while node is not None: print(node.data, end="") if node.next is not None: print(" -> ", end="") node = node.next print()# Function to find the Bell number at the given indexdef bellNumber(n): bell = [[0 for _ in range(n+1)] for _ in range(n+1)] bell[0][0] = 1 for i in range(1, n+1): bell[i][0] = bell[i-1][i-1] for j in range(1, i+1): bell[i][j] = bell[i-1][j-1] + bell[i][j-1] return bell[n][0]# Function to find the closest Bell number to a given node valuedef closestBell(n): bellNum = 0 while bellNumber(bellNum) < n: bellNum += 1 if bellNum == 0: return bellNumber(bellNum) else: prev = bellNumber(bellNum - 1) curr = bellNumber(bellNum) return prev if n - prev < curr - n else curr# Function to replace every node with its closest Bell numberdef replaceWithBell(node): while node is not None: node.data = closestBell(node.data) node = node.next# Driver codeif __name__ == "__main__": head = None # Creating the linked list head = push(head, 5) head = push(head, 2) head = push(head, 190) head = push(head, 7) head = push(head, 14) # Function call replaceWithBell(head) printList(head) |
C#
using System;// Node class for singly linked listclass Node{ public int data; public Node next; public Node(int data) { this.data = data; this.next = null; }}class GFG{ // Function to add a new node at the beginning of the linked list static Node Push(Node head_ref, int new_data) { Node new_node = new Node(new_data); new_node.next = head_ref; head_ref = new_node; return head_ref; } // Function to print the linked list static void PrintList(Node node) { while (node != null) { Console.Write(node.data); if (node.next != null) { Console.Write(" -> "); } node = node.next; } Console.WriteLine(); } // Function to find the Bell number at the given index static int BellNumber(int n) { int[][] bell = new int[n + 1][]; for (int i = 0; i <= n; i++) { bell[i] = new int[n + 1]; } bell[0][0] = 1; for (int i = 1; i <= n; i++) { bell[i][0] = bell[i - 1][i - 1]; for (int j = 1; j <= i; j++) { bell[i][j] = bell[i - 1][j - 1] + bell[i][j - 1]; } } return bell[n][0]; } // Function to find the closest Bell number to a given node value static int ClosestBell(int n) { int bellNum = 0; while (BellNumber(bellNum) < n) { bellNum++; } if (bellNum == 0) { return BellNumber(bellNum); } else { int prev = BellNumber(bellNum - 1); int curr = BellNumber(bellNum); return (n - prev < curr - n) ? prev : curr; } } // Function to replace every node with its closest Bell number static void ReplaceWithBell(Node node) { while (node != null) { node.data = ClosestBell(node.data); node = node.next; } } // Driver code static void Main() { Node head = null; // Creating the linked list head = Push(head, 5); head = Push(head, 2); head = Push(head, 190); head = Push(head, 7); head = Push(head, 14); // Function call ReplaceWithBell(head); PrintList(head); }} |
Javascript
// Javascript Implementation// Node class for singly linked listfunction Node(data) { this.data = data; this.next = null;}// Function to add a new node at the beginning of the linked listfunction push(head_ref, new_data) { var new_node = new Node(new_data); new_node.next = head_ref; head_ref = new_node; return head_ref;}// Function to print the linked listfunction printList(node) { while (node != null) { console.log(node.data + " "); if (node.next != null) { console.log("-> "); } node = node.next; }}// Function to find the Bell number at the given indexfunction bellNumber(n) { var bell = []; for (var i = 0; i <= n; i++) { bell[i] = []; for (var j = 0; j <= n; j++) { bell[i][j] = 0; } } bell[0][0] = 1; for (var i = 1; i <= n; i++) { bell[i][0] = bell[i - 1][i - 1]; for (var j = 1; j <= i; j++) { bell[i][j] = bell[i - 1][j - 1] + bell[i][j - 1]; } } return bell[n][0];}// Function to find the closest Bell number to a given node valuefunction closestBell(n) { var bellNum = 0; while (bellNumber(bellNum) < n) { bellNum += 1; } if (bellNum == 0) { return bellNumber(bellNum); } else { var prev = bellNumber(bellNum - 1); var curr = bellNumber(bellNum); return n - prev < curr - n ? prev : curr; }}// Function to replace every node with its closest Bell numberfunction replaceWithBell(node) { while (node != null) { node.data = closestBell(node.data); node = node.next; }}// Driver codevar head = null;// creating the linked listhead = push(head, 5);head = push(head, 2);head = push(head, 190);head = push(head, 7);head = push(head, 14);// Function callreplaceWithBell(head);printList(head);// This code is contributed by Tapesh(tapeshdua420) |
Output
15 -> 5 -> 203 -> 2 -> 5
Time Complexity: O(n3)
Auxiliary Space: O(n2)
Efficient approach: Space Optimized solution O(N)
In previous approach we are using 2D array to store the computations of subproblems but the current value is only dependent on the current and previous row of matrix so in this approach we are using 2 vector to store the current and previous rows of matrix.
Implementation steps:
- Initialize 2 vectors curr and prev of size N to store the current and previous rows of matrix.
- Now initialize the base case for n=0.
- Now iterate over subproblems to get the current value from previous computations.
- After every iteration assign values of prev to curr vector.
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Node structure of singly linked liststruct Node { int data; Node* next;};// Function to add a new node at the// beginning of the linked listvoid push(Node** head_ref, int new_data){ Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node;}// Function to print the linked listvoid printList(Node* node){ while (node != NULL) { cout << node->data; if (node->next != NULL) { cout << " -> "; } node = node->next; }}// Function to find the Bell number at// the given index in O(N) space complexityint bellNumber(int n){ // initialize vectors vector<int>curr(n + 1 , 0); vector<int>prev(n + 1 , 0); //Base case curr[0] = 1; prev[0] = 1; for (int i = 1; i <= n; i++) { curr[0] = prev[i - 1]; for (int j = 1; j <= i; j++) { curr[j] = prev[j - 1] + curr[j - 1]; } // assigning values to iterate further prev= curr; } return curr[0];}// Function to find the closest Bell number// to a given node valueint closestBell(int n){ int bellNum = 0; while (bellNumber(bellNum) < n) { bellNum++; } if (bellNum == 0) { return bellNumber(bellNum); } else { int prev = bellNumber(bellNum - 1); int curr = bellNumber(bellNum); return (n - prev < curr - n) ? prev : curr; }}// Function to replace every node with// its closest Bell numbervoid replaceWithBell(Node* node){ while (node != NULL) { node->data = closestBell(node->data); node = node->next; }}// Driver codeint main(){ Node* head = NULL; // Creating the linked list push(&head, 5); push(&head, 2); push(&head, 190); push(&head, 7); push(&head, 14); // Function call replaceWithBell(head); printList(head); return 0;} |
Time Complexity: O(n^2)
Auxiliary Space: O(n)
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!
