Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Given an integer k, return the minimum number of Fibonacci numbers whose sum is equal to k. The same Fibonacci number can be used multiple times.

Example:

Input:  19
Output: 3

Approach

Java

public class MaxFibNumSumIsK {
    public static void main(String[] args) {
        int k = 19;
        System.out.println(findMinFibonacciNumbers(k));
    }

//function to count the minimum
//fibonacci numbers whose sum is k
    static int findMinFibonacciNumbers(long k) {
        int fib[] = new int[50];
        fib[1] = 1;
        fib[2] = 1;
        for (int i = 3; i < 50; i++)
            fib[i] = fib[i - 1] + fib[i - 2];
        int i = 1;
        while (k >= fib[i])
            i++;
        int cnt = 0;
        i = i - 1;
        while (k > 0) {
            while (fib[i] > k)
                i--;
            k = k - fib[i];
            cnt++;
        }
        return cnt;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;


//function to count the minimum
//fibonacci numbers whose sum is k
long long findMinFibonacciNumbers(long long  k)
{
        long long  fib[50];
        fib[1]=1;
        fib[2]=1;
        for(long long  i=3;i<50;i++)
              fib[i]=fib[i-1]+fib[i-2];
        long long  i=1;
        while(k>=fib[i])
              i++;
        long long cnt=0;
        i=i-1;
       while(k)
         {
           while(fib[i]>k)
                 i--;
           k=k-fib[i];
          cnt++;
         }
        return cnt;
}

int main()
{
    int k = 19;
    cout<<findMinFibonacciNumbers(k);
    return 0;
}