FastPrep
Problem · Array

First Fibonacci Number at Least the Array Sum

Learn this problem
● EasyBitGo logoBitGoFULLTIMEOA

Problem statement

Given a nonempty array of nonnegative integers values, compute its sum S. Return the first Fibonacci number that is greater than or equal to S.

The sequence is defined by F0 = 0, F1 = 1, and Fk = F(k - 1) + F(k - 2) for k >= 2. “First” means the earliest value in this sequence, so a sum of 0 returns 0.

Function

firstFibonacciAtLeastSum(values: int[]) → long

Examples

Example 1

values = [4,1,3]return = 8

The sum is 8, which is itself a Fibonacci number.

Example 2

values = [2,2]return = 5

The sum is 4. The first Fibonacci number at least 4 is 5.

Constraints

  • 1 <= values.length <= 100000.
  • 0 <= values[i] <= 1000000000.
  • The sum of all values is at most 100000000000000.

More BitGo problems

drafts saved locally
public long firstFibonacciAtLeastSum(int[] values) {
    // Write your code here.
}
values[4,1,3]
expected8
checking account