Skip to main content
Talentd

Three Fibonacci Sum - Solution & Explanation

Easy9 min read
Practice this problem

Problem Statement

You are given an integer n.

The Fibonacci sequence starts with 0 and 1, and each subsequent number is the sum of the previous two numbers. Its first few terms are 0, 1, 1, 2, 3, 5, 8, 13, ....

Return true if n can be expressed as the sum of three consecutive terms in the Fibonacci sequence, and false otherwise.

 

Example 1:

Input: n = 16

Output: true

Explanation:

The three consecutive terms 3, 5, and 8 have a sum of 3 + 5 + 8 = 16.

Example 2:

Input: n = 8

Output: false

Explanation:

Although 1 + 2 + 5 = 8, these terms are not consecutive in the Fibonacci sequence. No three consecutive terms have a sum of 8.

Example 3:

Input: n = 2

Output: true

Explanation:

The first three terms have a sum of 0 + 1 + 1 = 2.

 

Constraints:

  • 1 <= n <= 109

Approach Overview

Problem Overview: You are given a target number and must decide whether it can be written as the sum of three Fibonacci numbers. The Fibonacci sequence grows exponentially, so only about 40 values fall below 10^9. That small set is the key to every approach below.

Approach 1: Brute Force Triple Loop (O(F^3) time, O(F) space)

Generate every Fibonacci number up to the target and store them in an array of size F. Use three nested loops to try every combination of three indices and check whether the three values sum to the target. This works because F is tiny, but it wastes work by re-checking the same combinations. Use it only to verify your reasoning on small inputs.

Approach 2: Fix One Value, Hash Lookup for the Other Two (O(F^2) time, O(F) space)

Build the Fibonacci list and a set of its values. Iterate over each Fibonacci number a as the first term. For each a, compute the remainder target - a, then iterate over the second term b and check whether target - a - b exists in the set with a hash lookup in O(1). This removes one loop level and turns the search into a quadratic scan with constant-time membership checks.

Approach 3: Sorted Array with Two Pointers (O(F^2) time, O(F) space)

The Fibonacci list is already sorted in increasing order, so you can replace the hash set with two pointers. Fix the first term, then place one pointer at the start and one at the end of the remaining suffix. Move the left pointer up when the pair sum is too small and the right pointer down when it is too large. This uses no hash table and keeps memory flat, which helps when you want a clean in-place search. It is the same asymptotic cost as Approach 2, so pick whichever you can explain more cleanly.

Recommended for interviews: Interviewers expect you to start with the brute force triple loop to show you understand the search space. The hash set or two-pointer version is the answer they want, because it cuts a level of iteration and shows you can exploit a sorted or bounded input. Mention that the Fibonacci list length is logarithmic in the target, which is why the quadratic solution is fast in practice. Related practice: math, hash table, and two pointers.

Solution

Thinking

n can be as large as 10^9, so counting up from 1 to n is not usable. Only a few dozen Fibonacci numbers stay within that bound, and checking every block of three consecutive terms is already enough.

Those three terms are tied together more tightly than a plain sum. The recurrence gives F_{i+2}=F_i+F_{i+1}, so the three-term sum is exactly twice the last term.

The question is then whether n is even and whether n/2 is a Fibonacci number. Those numbers can be stored in a hash set in advance, and each query is one membership test.

The Fibonacci sequence is defined by F_0=0, F_1=1, and F_{i+2}=F_i+F_{i+1}. The sum of three consecutive terms is

$ F_i+F_{i+1}+F_{i+2}=2F_{i+2}.

For i\ge 0, F_{i+2} runs through every Fibonacci number that is at least 1. Generate every Fibonacci number up to 10^9 in advance and store it in a hash set f. Return true when n is even and n/2\in f, and return false otherwise.

Preprocessing takes O(log M) time and O(log M) space, and each query takes O(1) time, where M=10^9$.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Triple LoopO(F^3)O(F)Quick check on small inputs or first draft
Fix One, Hash Set LookupO(F^2)O(F)General case, fastest to write in interviews
Two Pointers on Sorted ListO(F^2)O(F)Memory-sensitive or when no hash table is allowed

Video Solutions (5)

LeetCode Weekly Contest 523 Q1. Three Fibonacci Sum

ADevOpsEngineer2:03106 views
Video 1 of 5

Frequently Asked Questions

Is Three Fibonacci Sum easy or hard?
It is an easy problem with a 62.1 percent acceptance rate on FleetCode. The main challenge is realizing that the Fibonacci list is tiny, which makes a quadratic search fast. Once you see that, the implementation is only a few lines.
How to solve Three Fibonacci Sum in O(n)?
Because the Fibonacci list has only about log n elements, you cannot reduce the search below O(F^2) by treating it as a general array problem. To get close to linear behavior, reduce the search to one pass: for each candidate first term, check whether the remainder is a sum of two Fibonacci numbers using a precomputed set. Practically, the search stays near-linear in the target's bit length.
Three Fibonacci Sum Python and Java solution?
In Python, generate Fibonacci numbers with a while loop into a list, convert it to a set, and nest one loop over the list with a set lookup for the third term. In Java, build an ArrayList of longs, store values in a HashSet<Long>, and use the same nested loop with contains(). Use long types in Java because Fibonacci values can overflow int quickly.
What is the best approach for Three Fibonacci Sum?
The best approach is to precompute all Fibonacci numbers up to the target, then fix the first term and use a hash set to look up the remaining needed value. This runs in O(F^2) time, where F is the count of Fibonacci numbers below the target, which is roughly log of the target. Two pointers on the sorted list give the same complexity with O(F) space.
What data structure is used in Three Fibonacci Sum?
The solution uses an array or list to store the Fibonacci numbers in increasing order, and a hash set for constant-time membership checks. The two-pointer variant replaces the hash set with index pointers on the sorted array. Both structures take O(F) space.
What is the time complexity of Three Fibonacci Sum?
The optimal solution runs in O(F^2) time, where F is the number of Fibonacci values up to the target, about 40 for targets near 10^9. The brute force triple loop runs in O(F^3). Generating the Fibonacci list itself takes O(F) time and space.
Is Three Fibonacci Sum asked at Google, Amazon, or Meta?
This problem is tagged General on FleetCode and does not have confirmed company tags in the dataset. It tests basic number generation, hashing, and search pruning, which appear in many interview rounds. Treat it as a warm-up problem rather than a company-specific question.

Ready to solve this problem?

Practice Three Fibonacci Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Fibonacci Number