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/

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.
It is guaranteed that for the given constraints we can always find such fibonacci numbers that sum 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

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more