> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/greedy/sum-of-fibonacci-numbers.md).

# Sum Of Fibonacci Numbers

How many minimum numbers from `fibonacci` series are required such that sum of numbers should be equal to a given Number `N`?\
**Note : repetition of number is allowed.**

**Example:**

```
N = 4
Fibonacci numbers : 1 1 2 3 5 .... so on
here 2 + 2 = 4 
so minimum numbers will be 2 
```

```java
public class Solution {
    public int fibsum(int A) {
        // store fibonacci
        ArrayList<Integer> fibo = new ArrayList<Integer>();
        // generate fibonacci numbers
        int a = 0;
        int b = 1;
        int c = 1;
        while (c <= A) {
            fibo.add(c);
            a = b;
            b = c;
            c = a + b;
        }
        // store current sum
        int sum = 0;
        // count fibonacci numbers used
        int count = 0;
        while (sum < A) {
            int target = A - sum;
            int index = Collections.binarySearch(fibo, target);
            // if target doesn't exists use largest smaller value
            if (index < 0)
                index = (-1 * index) - 2;
            sum += fibo.get(index);
            count++;
        }
        return count;
    }
}
```