Given a singly linked list of integers, the task is to replace every node with its closest Fibonacci number and return the modified linked list.
Examples:
Input: List: 3->5->9->12->13->15->null
Output: 3->5->8->13->13->13->null
Explanation: The closest Fibonacci numbers for each node are:
- Node 1 (value = 3): Closest Fibonacci number = 3.
- Node 2 (value = 5): Closest Fibonacci number = 5.
- Node 3 (value = 9): Closest Fibonacci number = 8.
- Node 4 (value = 12): Closest Fibonacci number = 13.
- Node 5 (value = 13): Closest Fibonacci number = 13.
- Node 6 (value = 15): Closest Fibonacci number = 13.
Input: List : 1->2->3->4->5->null
Output: 1->2->3->5->5->null
Explanation: The closest Fibonacci numbers for each node are:
- Node 1 (value = 1): Closest Fibonacci number = 1.
- Node 2 (value = 2): Closest Fibonacci number = 2.
- Node 3 (value = 3): Closest Fibonacci number = 3.
- Node 4 (value = 4): Closest Fibonacci number = 5.
- Node 5 (value = 5): Closest Fibonacci number = 5.
Approach: This can be solved with the following idea:
This problem requires us to modify a linked list such that each node is replaced with its closest Fibonacci number. To solve this problem, we can start by creating an array of Fibonacci numbers that are greater than the maximum value in the linked list. We can then iterate over each node in the linked list, finding the closest Fibonacci number using the array we created.
Below are the steps for the above idea:
- Define a function getClosestFibonacci() that takes an integer n and a vector fib as input.
- Define an integer variable i and set it to 0.
- While the ith Fibonacci number in fib is less than n, increment i.
- If the ith Fibonacci number in fib is equal to n or if i is 0, return n.
- Otherwise, if n is closer to the i-1th Fibonacci number than the ith Fibonacci number, return the i-1th Fibonacci number. Otherwise, return the ith Fibonacci number.
- Define a function replaceWithClosestFibonacci() that takes a linked list head as input.
- Create a vector fib that contains all the Fibonacci numbers up to a certain limit. We can start by adding 0 and 1 to the vector, and then use a loop to generate additional Fibonacci numbers until we reach a limit (e.g., 1000000).
- Define a pointer curr and set it to head.
- While curr is not null, set the value of curr to the closest Fibonacci number using getClosestFibonacci() and the fib vector, and move to curr to the next node in the linked list.
- Return the modified linked list head.
Below is the implementation of the above approach:
C++
// C++ Implementation #include <iostream> #include <vector> using namespace std; // Structure of Node struct Node { int val; Node* next; Node( int v) : val(v), next(nullptr) { } }; // Function to find closest fibonacci // Number int getClosestFibonacci( int n, vector< int >& fib) { int i = 0; while (fib[i] < n) { i++; } if (fib[i] == n || i == 0) { return n; } else { return (n - fib[i - 1] < fib[i] - n) ? fib[i - 1] : fib[i]; } } // Function to replace node value with // closest number Node* replaceWithClosestFibonacci(Node* head) { vector< int > fib; fib.push_back(0); fib.push_back(1); int fibNum = 1; // set a limit for largest // Fibonacci number while (fibNum <= 1000000) { fib.push_back(fibNum); fibNum = fib[fib.size() - 1] + fib[fib.size() - 2]; } Node* curr = head; while (curr != nullptr) { curr->val = getClosestFibonacci(curr->val, fib); curr = curr->next; } return head; } // Function to print list void printList(Node* head) { Node* curr = head; while (curr != nullptr) { cout << curr->val << "->" ; curr = curr->next; } cout << "null" << endl; } // Driver code int main() { Node* head = new Node(3); head->next = new Node(5); head->next->next = new Node(9); head->next->next->next = new Node(12); head->next->next->next->next = new Node(13); head->next->next->next->next->next = new Node(15); // Function call head = replaceWithClosestFibonacci(head); printList(head); return 0; } |
Java
// Java Implementation import java.util.ArrayList; import java.util.List; // Structure of Node class Node { int val; Node next; Node( int v) { val = v; next = null ; } } public class Main { // Function to find closest fibonacci Number static int getClosestFibonacci( int n, List<Integer> fib) { int i = 0 ; while (fib.get(i) < n) { i++; } if (fib.get(i) == n || i == 0 ) { return n; } else { return (n - fib.get(i - 1 ) < fib.get(i) - n) ? fib.get(i - 1 ) : fib.get(i); } } // Function to replace node value with closest number static Node replaceWithClosestFibonacci(Node head) { List<Integer> fib = new ArrayList<>(); fib.add( 0 ); fib.add( 1 ); int fibNum = 1 ; // set a limit for largest Fibonacci number while (fibNum <= 1000000 ) { fib.add(fibNum); fibNum = fib.get(fib.size() - 1 ) + fib.get(fib.size() - 2 ); } Node curr = head; while (curr != null ) { curr.val = getClosestFibonacci(curr.val, fib); curr = curr.next; } return head; } // Function to print list static void printList(Node head) { Node curr = head; while (curr != null ) { System.out.print(curr.val + "->" ); curr = curr.next; } System.out.println( "null" ); } // Driver code public static void main(String[] args) { Node head = new Node( 3 ); head.next = new Node( 5 ); head.next.next = new Node( 9 ); head.next.next.next = new Node( 12 ); head.next.next.next.next = new Node( 13 ); head.next.next.next.next.next = new Node( 15 ); // Function call head = replaceWithClosestFibonacci(head); printList(head); } } |
Python3
# Python3 Implementation import math # Structure of Node class Node: def __init__( self , v): self .val = v self . next = None # Function to find closest fibonacci # Number def getClosestFibonacci(n, fib): i = 0 while fib[i] < n: i + = 1 if fib[i] = = n or i = = 0 : return n else : return fib[i - 1 ] if (n - fib[i - 1 ] < fib[i] - n) else fib[i] # Function to replace node value with # closest number def replaceWithClosestFibonacci(head): fib = [ 0 , 1 ] fibNum = 1 # set a limit for largest # Fibonacci number while fibNum < = 1000000 : fib.append(fibNum) fibNum = fib[ - 1 ] + fib[ - 2 ] curr = head while curr ! = None : curr.val = getClosestFibonacci(curr.val, fib) curr = curr. next return head # Function to print list def printList(head): curr = head while curr ! = None : print (curr.val, end = "->" ) curr = curr. next print ( "null" ) # Driver code if __name__ = = '__main__' : head = Node( 3 ) head. next = Node( 5 ) head. next . next = Node( 9 ) head. next . next . next = Node( 12 ) head. next . next . next . next = Node( 13 ) head. next . next . next . next . next = Node( 15 ) # Function call head = replaceWithClosestFibonacci(head) printList(head) |
C#
//using c# approach using System; using System.Collections.Generic; // Structure of Node public class Node { public int val; public Node next; public Node( int v) { val = v; next = null ; } } public class GFG { // Function to find closest fibonacci number public static int GetClosestFibonacci( int n, List< int > fib) { int i = 0; while (fib[i] < n) { i++; } if (fib[i] == n || i == 0) { return n; } else { return (n - fib[i - 1] < fib[i] - n) ? fib[i - 1] : fib[i]; } } // Function to replace node value with the closest fibonacci number public static Node ReplaceWithClosestFibonacci(Node head) { List< int > fib = new List< int > { 0, 1 }; int fibNum = 1; // Set a limit for the largest Fibonacci number while (fibNum <= 1000000) { fib.Add(fibNum); fibNum = fib[fib.Count - 1] + fib[fib.Count - 2]; } Node curr = head; while (curr != null ) { curr.val = GetClosestFibonacci(curr.val, fib); curr = curr.next; } return head; } // Function to print the list public static void PrintList(Node head) { Node curr = head; while (curr != null ) { Console.Write(curr.val + "->" ); curr = curr.next; } Console.WriteLine( "null" ); } // Driver code public static void Main() { Node head = new Node(3); head.next = new Node(5); head.next.next = new Node(9); head.next.next.next = new Node(12); head.next.next.next.next = new Node(13); head.next.next.next.next.next = new Node(15); // Function call head = ReplaceWithClosestFibonacci(head); PrintList(head); } } |
Javascript
// Structure of Node class Node { constructor(v) { this .val = v; this .next = null ; } } // Function to find closest fibonacci Number function getClosestFibonacci(n, fib) { let i = 0; while (fib[i] < n) { i++; } if (fib[i] === n || i === 0) { return n; } else { return (n - fib[i - 1] < fib[i] - n) ? fib[i - 1] : fib[i]; } } // Function to replace node value with closest number function replaceWithClosestFibonacci(head) { const fib = [0, 1]; let fibNum = 1; // set a limit for the largest Fibonacci number while (fibNum <= 1000000) { fib.push(fibNum); fibNum = fib[fib.length - 1] + fib[fib.length - 2]; } let curr = head; while (curr !== null ) { curr.val = getClosestFibonacci(curr.val, fib); curr = curr.next; } return head; } // Function to print list function printList(head) { let curr = head; while (curr !== null ) { console.log(curr.val + "->" ); curr = curr.next; } console.log( "null" ); } // Node class is defined above // Driver code const head = new Node(3); head.next = new Node(5); head.next.next = new Node(9); head.next.next.next = new Node(12); head.next.next.next.next = new Node(13); head.next.next.next.next.next = new Node(15); // Function call replaceWithClosestFibonacci(head); printList(head); |
3->5->8->13->13->13->null
Time Complexity: O(n*logn)
Auxiliary Space: O(k)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!