Minimum Number of Fibonacci Numbers
Interesting problem, fresh out of the oven: https://leetcode.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/
The constraint might seem large (10^9), however when you think about the exponential growth of the Fibonacci numbers, you soon realize that the max number of Fibonacci numbers that you'll be operating with is 45, hence it is actually very small.
Compute all the Fibonacci numbers up to k (DP-style, not recursively pls), store them in a cache (to be used later) and also sort them in descending order. Do a DFS approach controlling the recursion with either the index of the sorted Fibonacci numbers, or the k itself (subtracting it as much as you can). Use the cache to optimize the search space. Works fast. Code is below, cheers, ACC.
public class Solution
{
public int FindMinFibonacciNumbers(int k)
{
Hashtable cache = new Hashtable();
int[] fibarr = GenFin(k, cache);
return FindMinFibonacciNumbers(k, cache, fibarr, 0);
}
private int FindMinFibonacciNumbers(int k, Hashtable cache, int[] fib, int index)
{
if (k == 0 || index < 0) return 0;
if (cache.ContainsKey(k)) return 1;
if (k - fib[index] < 0) return FindMinFibonacciNumbers(k, cache, fib, index + 1);
return 1 + FindMinFibonacciNumbers(k - fib[index], cache, fib, index);
}
private int[] GenFin(int k, Hashtable cache)
{
SortedList<int, int> fib = new SortedList<int, int>();
int f1 = 1;
int f2 = 2;
fib.Add(f1, f1);
cache.Add(f1, true);
while (f2 <= k)
{
fib.Add(f2, f2);
cache.Add(f2, true);
int temp = f1;
f1 = f2;
f2 += temp;
}
int[] fibarr = new int[fib.Count];
for (int i = 0; i < fib.Count; i++)
{
fibarr[i] = fib.ElementAt(fib.Count - i - 1).Key;
}
return fibarr;
}
}
1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K
Medium
Given the number
k, return the minimum number of Fibonacci numbers whose sum is equal to k, whether a Fibonacci number could be used multiple times.
The Fibonacci numbers are defined as:
- F1 = 1
- F2 = 1
- Fn = Fn-1 + Fn-2 , for n > 2.
k.
Example 1:
Input: k = 7 Output: 2 Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ... For k = 7 we can use 2 + 5 = 7.
Example 2:
Input: k = 10 Output: 2 Explanation: For k = 10 we can use 2 + 8 = 10.
Example 3:
Input: k = 19 Output: 3 Explanation: For k = 19 we can use 1 + 5 + 13 = 19.
Constraints:
1 <= k <= 10^9
Accepted
4,104
Submissions
7,492
The constraint might seem large (10^9), however when you think about the exponential growth of the Fibonacci numbers, you soon realize that the max number of Fibonacci numbers that you'll be operating with is 45, hence it is actually very small.
Compute all the Fibonacci numbers up to k (DP-style, not recursively pls), store them in a cache (to be used later) and also sort them in descending order. Do a DFS approach controlling the recursion with either the index of the sorted Fibonacci numbers, or the k itself (subtracting it as much as you can). Use the cache to optimize the search space. Works fast. Code is below, cheers, ACC.
public class Solution
{
public int FindMinFibonacciNumbers(int k)
{
Hashtable cache = new Hashtable();
int[] fibarr = GenFin(k, cache);
return FindMinFibonacciNumbers(k, cache, fibarr, 0);
}
private int FindMinFibonacciNumbers(int k, Hashtable cache, int[] fib, int index)
{
if (k == 0 || index < 0) return 0;
if (cache.ContainsKey(k)) return 1;
if (k - fib[index] < 0) return FindMinFibonacciNumbers(k, cache, fib, index + 1);
return 1 + FindMinFibonacciNumbers(k - fib[index], cache, fib, index);
}
private int[] GenFin(int k, Hashtable cache)
{
SortedList<int, int> fib = new SortedList<int, int>();
int f1 = 1;
int f2 = 2;
fib.Add(f1, f1);
cache.Add(f1, true);
while (f2 <= k)
{
fib.Add(f2, f2);
cache.Add(f2, true);
int temp = f1;
f1 = f2;
f2 += temp;
}
int[] fibarr = new int[fib.Count];
for (int i = 0; i < fib.Count; i++)
{
fibarr[i] = fib.ElementAt(fib.Count - i - 1).Key;
}
return fibarr;
}
}
Comments
Post a Comment