Find the Minimum Number of Fibonacci Numbers Whose Sum Is K LeetCode solution in C++

1
class Solution {
2
 public:
3
  int findMinFibonacciNumbers(int k) {
4
    vector<int> fibb;
5
    int a = 1;
6
    int b = 1;
7
    fibb.push_back(a);
8
    fibb.push_back(b);
9
    int next = a + b;
10

11
    while (next <= k) {
12
      fibb.push_back(next);
13
      a = b;
14
      b = next;
15
      next = a + b;
16
    }
17

18
    int res = 0;
19
    int j = fibb.size() - 1;
20
    while (j >= 0 and k > 0) {
21
      if (fibb[j] <= k) {
22
        k -= fibb[j];
23
        res++;
24
      }
25
      j--;
26
    }
27

28
    return res;
29
  }
30
};