1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K
Problem Description
The problem presents a scenario where you are provided an integer k, and your task is to find the minimum number of Fibonacci numbers that can be combined to equal k. Importantly, it's allowed to use the same Fibonacci number more than once in the sum.
The Fibonacci sequence mentioned here starts with F1 = 1 and F2 = 1, and each subsequent number is the sum of the previous two (Fn = Fn-1 + Fn-2 for n > 2). The question guarantees that it's always possible to find a combination of Fibonacci numbers that sum up to the given k.
To put it simply, the challenge is to break down the number k into a sum consisting of the least possible number of elements from the Fibonacci sequence.
Intuition
The intuition behind approaching this problem is to utilize a greedy algorithm. Since we need to minimize the number of Fibonacci numbers, we should always try to fit the largest possible Fibonacci number into the sum without exceeding k. Each time we find such a number, we subtract it from k and continue with the process until k is reduced to 0. This approach ensures that at each step, the largest possible chunk is taken out of k, thereby ensuring the minimum number of steps.
To implement this method, we'll need to generate Fibonacci numbers on the fly and keep track of the two most recent ones, as any Fibonacci number can be obtained by summing up the previous two. As soon as we calculate a Fibonacci number that is larger than k, we'll set aside the last number computed as the largest Fibonacci number to be used and subtract it from k. This step is recursively repeated until k becomes 0, at which point the total count of Fibonacci numbers used gives us the answer.
Which of these pictures shows the visit order of a depth-first search?
Solution Approach
The implementation of the solution follows a recursive depth-first search (DFS) strategy with a greedy algorithm to find the minimum number of Fibonacci numbers that sum up to k.
Here is a step-by-step walkthrough of the solution code provided:
-
Define a recursive function
dfsthat takes the current value ofkas its argument:-
If
kis less than 2, we can directly returnkbecause if it's either 0 or 1, it's already a Fibonacci number and no further decomposition is needed. -
Initialize two variables
aandb, both with the value1, corresponding to the first two Fibonacci numbers (F1andF2). -
Use a
whileloop to find the largest Fibonacci number that is less than or equal tok. This is done by continuously updatingaandbwith the next Fibonacci numbers in the sequence (wherebtakes the value ofa + bandatakes the previous value ofb). Whenbbecomes larger thank, the loop breaks. -
The function then calls itself with the reduced value
k - a, which iskminus the largest Fibonacci number less than or equal tok. This step represents subtracting the largest Fibonacci chunk from the current number. It also adds1to the result, counting the used Fibonacci number.
-
-
The outer function
findMinFibonacciNumbersdefined in theSolutionclass invokes thedfsfunction with the valuekand returns its result. The recursion will eventually reachkequal to 0, at which point the recursion unwinds and the total count of the Fibonacci numbers used is obtained.
The algorithm uses a recursive DFS approach to explore all possibilities in reducing k with Fibonacci chunks and the greedy strategy ensures that the solution is both effective and optimal for the given problem constraints. There is no need for additional data structures beyond the variables holding the two most recent Fibonacci numbers and the recursive stack.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
81public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
121class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85Example Walkthrough
Let's consider an example with k = 10. Our goal is to find the minimum number of Fibonacci numbers that, when summed, equal k.
We start with the first two Fibonacci numbers being 1 (F1 and F2). As per the steps mentioned:
-
Since
kis greater than 2, we proceed to find the largest Fibonacci number less than or equal tok. We keep generating Fibonacci numbers until we find that8is the largest Fibonacci number less than or equal to10. Here's the sequence:1, 1, 2, 3, 5, 8. -
We now subtract this largest Fibonacci number from
k:10 - 8 = 2. This means we've used1Fibonacci number (8) so far. -
We now set
kto the result from the subtraction above, which is2. We begin the process again to find the largest Fibonacci number less than or equal to2. In this case,2itself is a Fibonacci number. -
We subtract
2fromk, resulting in0:2 - 2 = 0. We've used one more Fibonacci number (2).
At this point, our sum of Fibonacci numbers equals the original k (8 + 2 = 10), and k has been reduced to 0. We have used 2 Fibonacci numbers altogether (number 8 and number 2), and since we cannot lower the count further, the minimum number of Fibonacci numbers that sum up to the given k is 2.
Thus, for k = 10, the minimum number of Fibonacci numbers required is 2. This illustrates the greedy approach that the algorithm uses by choosing the largest possible Fibonacci numbers starting from the biggest one less than or equal to k to minimize the total count.
Solution Implementation
1class Solution:
2 def findMinFibonacciNumbers(self, k: int) -> int:
3 # Helper function to find the minimum number of Fibonacci numbers whose sum is equal to k.
4 def find_min_fib_nums(k):
5 # Base case: if k is less than 2, it's already a Fibonacci number (0 or 1).
6 if k < 2:
7 return k
8
9 # Initialize two Fibonacci numbers, a and b, starting with 1.
10 a, b = 1, 1
11
12 # Iterate to find the largest Fibonacci number less than or equal to k.
13 while b <= k:
14 # Update the previous two Fibonacci numbers.
15 a, b = b, a + b
16
17 # Once b is larger than k, a is the largest Fibonacci number less than or equal to k.
18 # Use recursive call to find the sum of Fibonacci numbers for the remainder (k - a).
19 # The 1 added represents the count for the Fibonacci number 'a' used in the sum.
20 return 1 + find_min_fib_nums(k - a)
21
22 # Initiate the recursive process starting with the original input k.
23 return find_min_fib_nums(k)
241class Solution {
2 // Method to find the minimum number of Fibonacci numbers whose sum is equal to k.
3 public int findMinFibonacciNumbers(int k) {
4 // Base case: for k < 2, the result would be k itself as it is the sum
5 // of 0 and 1, or just 1 in the Fibonacci sequence.
6 if (k < 2) {
7 return k;
8 }
9
10 int first = 1; // Initialize the first Fibonacci number.
11 int second = 1; // Initialize the second Fibonacci number.
12
13 // Generate Fibonacci numbers until the current number exceeds or is equal to k.
14 while (second <= k) {
15 second = first + second; // Update the second number to the next Fibonacci number.
16 first = second - first; // Update the first number to the previous second number.
17 }
18
19 // Recursive call, find the remaining number (k - first) which is the nearest
20 // Fibonacci number less than k, and add 1 to the count.
21 return 1 + findMinFibonacciNumbers(k - first);
22 }
23}
241class Solution {
2public:
3 // Function to find the minimum number of Fibonacci numbers whose sum is equal to k.
4 int findMinFibonacciNumbers(int k) {
5 // If k is less than 2, it's already a Fibonacci number (either 0 or 1).
6 if (k < 2) return k;
7
8 // Initialize two variables to represent the last two Fibonacci numbers.
9 int prev = 1; // Represents the second-to-last Fibonacci number.
10 int curr = 1; // Represents the last Fibonacci number.
11
12 // Generate Fibonacci numbers until the current number is greater than k.
13 while (curr <= k) {
14 int temp = curr;
15 curr = prev + curr; // Update curr to the next Fibonacci number.
16 prev = temp; // Update prev to the previous curr value.
17 }
18
19 // After finding the first Fibonacci number greater than k, subtract the
20 // second-to-last Fibonacci number from k (prev is the largest Fibonacci number less than or equal to k).
21 // Add 1 to the result since we include the prev Fibonacci number in the sum,
22 // and recursively call the function to find the rest.
23 return 1 + findMinFibonacciNumbers(k - prev);
24 }
25};
261// Array of Fibonacci numbers in descending order.
2const fibonacciNumbers = [
3 1836311903, 1134903170, 701408733, 433494437, 267914296, 165580141, 102334155, 63245986,
4 39088169, 24157817, 14930352, 9227465, 5702887, 3524578, 2178309, 1346269, 832040, 514229,
5 317811, 196418, 121393, 75025, 46368, 28657, 17711, 10946, 6765, 4181, 2584, 1597, 987, 610,
6 377, 233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1,
7];
8
9/**
10 * Finds the minimum number of Fibonacci numbers whose sum is equal to a given integer k.
11 * @param {number} k - The target number to represent as a sum of Fibonacci numbers.
12 * @returns {number} - The minimum count of Fibonacci numbers that sum up to k.
13 */
14function findMinFibonacciNumbers(k: number): number {
15 let resultCount = 0; // Initialize the count of Fibonacci numbers used.
16
17 // Iterate over the array of Fibonacci numbers.
18 for (const number of fibonacciNumbers) {
19 // If the current Fibonacci number can be subtracted from k, use it.
20 if (k >= number) {
21 k -= number; // Subtract the current number from k.
22 resultCount++; // Increment the count as we have used one Fibonacci number.
23
24 // If k becomes zero, we found a complete sum, so break the loop.
25 if (k === 0) {
26 break;
27 }
28 }
29 }
30
31 // Return the total count of Fibonacci numbers used to represent k.
32 return resultCount;
33}
34Which of these properties could exist for a graph but not a tree?
Time and Space Complexity
Time Complexity
The time complexity of the given solution largely depends on how many recursive calls we make, which in turn is based on the value of k and the Fibonacci numbers generated.
For each call to dfs(k), we perform a loop that generates Fibonacci numbers until the largest Fibonacci number less than or equal to k is found. The number of iterations of this loop is bounded by the index n of the Fibonacci number that is closest to k in value, where F_n ≈ φ^n / sqrt(5) and φ (phi) is the golden ratio (1 + sqrt(5)) / 2 ≈ 1.618.
The time complexity of generating each Fibonacci number is O(1), but finding the correct Fibonacci number for subtraction requires looping over the Fibonacci sequence, which has a time complexity of O(log(k)) since the Fibonacci numbers grow exponentially.
Recursively, we subtract the found Fibonacci number from k and repeat the process. In the worst case, we might have to go as far as the first Fibonacci numbers for each recursive call if k is a large Fibonacci number itself, leading to a time complexity of O(log(k)) * O(log(k)) = O(log^2(k)).
Space Complexity
The space complexity of the solution is determined by the maximum depth of the recursion stack. Since we subtract the largest Fibonacci number less than or equal to k at every step, the maximum depth of the recursion is also O(log(k)). Every call to dfs(k) uses O(1) space, except for the space used in the recursive call stack.
Thus, the total space complexity is O(log(k)).
Learn more about how to find time and space complexity quickly using problem constraints.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.