“This is the 17th day of my participation in the First Challenge 2022.

Topic describes

This is the LeetCode 1414 and the minimum Fibonacci number for K, of medium difficulty.

Tag: “Math”, “dichotomy”, “greed”

Given the number k, return the minimum number of Fibonacci numbers that sum to k, where each Fibonacci number can be used multiple times.

Fibonacci numbers are defined as:

  • F1 = 1
  • F2 = 1
  • Fn = fn-1 + fn-2, where n > 2.

The data guarantees that for a given k, a feasible solution can be found.

Example 1:

Input: k = 7 output: 2 explanation: Fibonacci numbers are: 1,1,2,3,5,8,13... For k = 7, we get 2 plus 5 is equal to 7.Copy the code

Example 2:

Input: k = 10 Output: 2 Explanation: For k = 10, we get 2 + 8 = 10.Copy the code

Example 3:

Input: k = 19 Output: 3 Explanation: For k = 19, we get 1 + 5 + 13 = 19.Copy the code

Tip:


  • 1 < = k < = 1 0 9 1 <= k <= 10^9

Hit the clock + greedy + 2

Static = Fibonacci = 10910^9109; static = Fibonacci = 10910^9109; static = Fibonacci = 10910^9109;

Then consider how to use the (repeatable) numbers in the list to make k.

An intuitive idea is to find the largest number in the list that does not exceed K each time, and subtract k until k is reduced to 000. The number of subtract is the answer.

For “find the largest number from list up to k”, use “binary”.

The following proves the correctness of this practice:

It is assumed that the feasible solution sequence obtained by this method is A (sequence length is Ansansans), and the real optimal solution sequence is B (sequence length is minminmin).

Assuming that the length of the two is not equal (only ANS >minans >minans >min), this means that when we remove the same elements between A and B, the sequence of the remaining elements is as follows:

  • “AThe sum of the remaining elements of the sequence is equal toBSum of the remaining elements of the sequence “;
  • “ANumber of remaining elements in sequence “greater than”BNumber of remaining elements in the sequence “.

A prime is the sequence of remaining elements of A, and B prime is the sequence of remaining elements of B.

We know that the largest number in A prime must be greater than the largest number in B prime. It cannot be equal relation (equal elements are removed), nor can it be less than relation, otherwise when constructing A sequence, it will be constructed in the direction of generating B sequence.

However, it is still difficult to prove that there is no Combination of Fibonacci numbers satisfying the above conclusion.

We can start from the property of Fibonacci numbers to find feasible solutionsAThen it is proved that there is no scheme ratio that does not satisfy this propertyABetter.

For the feasible solution A, since we “choose the largest number not exceeding the current k every time”, there must be no two adjacent Fibonacci numbers in the necessarily feasible solution. Otherwise, fi+2f_{I +2} FI +2 will be selected before fif_ifi and FI +1f_{I +1} FI +1.

At the same time, Because the fi = fi – 1 + 2 f_i fi – = f_ {1} I – + f_ {2} I – fi – fi = fi – 1 + 2, fi + fi – 1 + 1 = fi f_ {I + 1} = f_ {I} + f_ {1} I – fi + fi – 1 and + 1 = fi Fi + + 1 + 2 = fi fif_ {2} I + = f_ + f_ {I + 1} {I} fi + + 1 + 2 = fi fi available + 1 + 2 ∗ fi = fi fi – 22 * f_ {I} = f_ f_ {I + 1} + {2} I – 2 ∗ fi = fi – fi + 1 + 2.

Otherwise, fi+1f_{I +1} FI +1 will be selected before FIF_IFi because “the maximum number of current K will not be selected each time”.

This reasoning is also true for the boundary special value 111. If there are more than 111 in the feasible solution A, f3=2f_3=2f3=2 will inevitably be selected first because “the maximum number of k is not selected each time”.

Then according to the “Fibonacci number odd even sum”, we can know:
a 1 + a 3 + . . . + a 2 n – 1 = a 2 n a_1 + a_3 + … + a_{2n – 1} = a_{2n} 和
a 2 + a 4 + . . . + a 2 n = a 2 n + 1 – 1 a_2 + a_4 + … + a_{2n} = a_{2n+1} – 1 .

In summary, it can be proved that there is no specific feasible solutionAShorter optimal solution.

Code:

class Solution {
    static List<Integer> list = new ArrayList<>();
    static {
        list.add(1);
        int a = 1, b = 1;
        while (b <= (int)1e9) {
            intc = a + b; a = b; b = c; list.add(c); }}public int findMinFibonacciNumbers(int k) {
        int ans = 0;
        while(k ! =0) {
            int l = 0, r = list.size() - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (list.get(mid) <= k) l = mid;
                else r = mid - 1;
            }
            k -= list.get(r);
            ans++;
        }
        returnans; }}Copy the code
  • Time complexity: let the value not exceed
    1 0 9 10 ^ 9     The Fibonacci number of phi is zeroC, the complexity is
    O ( log ⁡ k ∗ log ⁡ C ) O(\log{k} * \log{C})
  • Space complexity: O(C)O(C)O(C)

greedy

In the above method, because all Fibonacci numbers whose values do not exceed 10910^9109 are preprocessed, “the maximum number whose values do not exceed K” cannot be obtained directly, so another layer of “dichotomy” is needed.

O(log⁡k)O(\log{k})O(logk) time complexity and O(1)O(1)O(1) space complexity can be achieved by using the recursive properties of the Fibonacci sequence and the conclusion that the optimal solution to k does not contain repeated numbers without preprocessing.

Code:

class Solution {
    public int findMinFibonacciNumbers(int k) {
        int a = 1, b = 1;
        while (b <= k) {
            int c = a + b;
            a = b; b = c;
        }
        int ans = 0;
        while(k ! =0) {
            if (k >= b) {
                k -= b; ans++;
            }
            int c = b - a;
            b = a; a = c;
        }
        returnans; }}Copy the code
  • O(log⁡k)O(\log{k})O(logk)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No.1414 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.