Count Fibonacci Numbers in an Array

Title: Count Fibonacci Numbers in an Array

Counting Fibonacci numbers in an array is a classic warm-up that mixes two ideas you will reuse in dozens of interview questions: generating the Fibonacci sequence and performing fast membership checks. In this guide, we will walk through a clean Java implementation that pre-computes every Fibonacci number up to the array’s maximum value and then scans the input once to count how many of its elements belong to the sequence.

You will learn the problem statement, a step-by-step approach, a full compilable Java program, a dry-run trace, two worked examples, common pitfalls specific to this algorithm, edge cases to probe, interview follow-ups, and the time and space complexity trade-offs. By the end, you will be able to code this on a whiteboard and defend each decision you made along the way.

Understanding the Problem

The Fibonacci sequence begins with 0 and 1, and every subsequent term is the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, and so on. Given an input array of integers, we need to return how many of its elements appear in this sequence.

The naive solution regenerates the Fibonacci sequence for every element, which is wasteful because the sequence depends only on the array’s maximum value. A better approach generates the sequence once, stores every Fibonacci number from 0 up to that maximum in a HashSet, and then checks each element against the set in constant time.

Approach to Count Fibonacci Numbers

Here are the steps we will follow:

1. Guard against a null or empty input and return 0 if the array has no elements.
2. Scan the array once to find its maximum value, which bounds the Fibonacci numbers we will need.
3. Build a HashSet<Integer> containing every Fibonacci number from 0 up to that maximum, using two running variables a and b.
4. Initialize a counter count to zero.
5. Iterate through the array a second time and increment count whenever the current element is contained in the set.
6. Return count.

Java Program to Count Fibonacci Numbers in an Array

Below is the full, compilable Java program that implements the approach described above.

import java.util.HashSet;
import java.util.Set;

public class CountFibonacciNumbers {

    public static int countFibonacci(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            return 0;
        }
        int max = numbers[0];
        for (int value : numbers) {
            if (value > max) {
                max = value;
            }
        }
        Set<Integer> fibonacciSet = buildFibonacciSet(max);
        int count = 0;
        for (int value : numbers) {
            if (fibonacciSet.contains(value)) {
                count++;
            }
        }
        return count;
    }

    private static Set<Integer> buildFibonacciSet(int limit) {
        Set<Integer> fibonacci = new HashSet<>();
        int a = 0;
        int b = 1;
        while (a <= limit) {
            fibonacci.add(a);
            int next = a + b;
            a = b;
            b = next;
        }
        return fibonacci;
    }

    public static void main(String[] args) {
        int[] numbers = {1, 4, 8, 13, 2, 10, 21};
        System.out.println("Fibonacci count: " + countFibonacci(numbers));
    }
}

Explanation of the Program

The two imports pull in HashSet and its interface Set from java.util. The class CountFibonacciNumbers exposes a single public method, countFibonacci, that takes an int[] and returns the number of its elements that are Fibonacci numbers.

The method first guards against a null reference and an empty array, returning 0 in both cases so callers never see an exception for a benign input. It then runs a linear scan to find max, the upper bound for the Fibonacci numbers we care about. Any Fibonacci number larger than max cannot appear in the input, so we never need to generate it.

Next, buildFibonacciSet uses two running integers a and b to walk the sequence. On each iteration it adds a to the set, computes next = a + b, and slides the window forward: a becomes b and b becomes next. The loop stops once a exceeds limit, so the set contains exactly the Fibonacci numbers from 0 through limit.

Finally, a second pass over the input increments count whenever fibonacciSet.contains(value) returns true. The main method demonstrates the function on a seven-element array and prints the result.

Step-by-Step Trace

Let us trace the counting loop on the input {6, 5, 10, 2, 7, 8}. The maximum is 10, so buildFibonacciSet(10) returns {0, 1, 2, 3, 5, 8}. The expected answer is 3 because only 5, 2, and 8 are Fibonacci numbers.

At the end of iteration i, count holds the number of Fibonacci numbers in numbers[0..i]. That invariant is what guarantees the final return value is correct no matter how many Fibonacci numbers the input contains.

Examples

Example 1: Mixed Fibonacci and Non-Fibonacci Values

The input mixes Fibonacci numbers 1, 8, 13, 2, 21 with the non-Fibonacci values 4 and 10, so the method returns 5.

int[] numbers = {1, 4, 8, 13, 2, 10, 21};
int result = countFibonacci(numbers);
System.out.println(result);
// Output: 5

Example 2: No Fibonacci Numbers Present

Every value in this input sits between two consecutive Fibonacci numbers but is itself not Fibonacci, so the method returns 0.

int[] numbers = {4, 6, 9, 10, 12};
int result = countFibonacci(numbers);
System.out.println(result);
// Output: 0

Common Mistakes to Avoid

Candidates lose points on this problem in a few predictable ways. Watch out for the following.

• Regenerating Fibonacci per element – calling isFibonacci(value) inside the counting loop forces an O(n * k) solution where k is the number of Fibonacci numbers up to max. Build the set once outside the loop and keep membership checks O(1).
• Using a List instead of a HashSet – list.contains(value) is a linear scan and silently makes the algorithm quadratic. Pick HashSet whenever you need membership and do not care about order.
• Forgetting that 0 is a Fibonacci number – stopping the generator when a is already 1 drops 0 from the set and under-counts inputs that contain zero. Start the sequence with a = 0, b = 1 and add a before advancing.
• Integer overflow near Integer.MAX_VALUE – once b exceeds roughly 1.8 billion, a + b wraps around and either infinite-loops or inserts bogus negative values into the set. Switch a and b to long (or guard the sum) if the input can hold values near Integer.MAX_VALUE.
• Using >= instead of > when tracking max – works but reassigns max on every equal value, which is wasteful. Use > so the write only happens when strictly needed.

Edge Cases to Test

Walk through this checklist before you declare the solution finished. A good interviewer will quietly tally how many of these you mention unprompted.

• Empty array
• Single-element array
• Array of only Fibonacci numbers
• Array with no Fibonacci numbers
• Zero present as a value
• Duplicate values in the input
• All negative elements
• Values near Integer.MAX_VALUE
• Null array reference

Additional Considerations

The total running time is O(n + log(max)) where n is the length of the input and max is its largest value. The log(max) term comes from the exponential growth of Fibonacci numbers: there are only about 45 of them inside the 32-bit int range, so building the set is effectively constant work for any realistic input.

The auxiliary space is O(log(max)) for the HashSet. If memory is tight and the array is small, a sorted array of Fibonacci numbers plus binary search gives the same big-O time with less overhead than a HashSet. For very large max values that overflow int, promote a, b, and next to long and store the set as Set<Long>.

Note that negative numbers are never Fibonacci under the standard definition, so the current logic correctly skips them without any extra branch. If the array is entirely negative, max will be negative, buildFibonacciSet will loop zero times, and the final count will be 0.

Interview Follow-up Questions

Expect the interviewer to probe variants that change the shape of the problem. Here are the ones you should rehearse.

• What if you also need the indices of the Fibonacci elements, not just the count? – collect them into an ArrayList<Integer> during the second pass; everything else stays the same.
• What if the array can contain values up to 10^18? – switch a, b, and the set element type to long, since Fibonacci grows past Integer.MAX_VALUE at F(47).
• What if you cannot use extra memory for a HashSet? – use the closed-form check: a non-negative integer n is Fibonacci iff 5*n*n + 4 or 5*n*n - 4 is a perfect square, which runs in O(1) per element with no auxiliary storage.
• What if the input arrives as a stream of unknown length? – pre-build the Fibonacci set up to Long.MAX_VALUE (still fewer than 100 values) once, then increment a running counter as each element arrives.
• What if the array has billions of entries and must be processed in parallel? – partition the input, count Fibonacci hits in each partition against a shared immutable set, then sum the partial counts; the work is embarrassingly parallel.

Conclusion

Counting Fibonacci numbers in an array is a small problem that rewards clean thinking. Pre-compute the sequence once, use a HashSet for constant-time lookups, and the whole solution collapses to a two-pass linear scan with a tiny auxiliary set. Reach for the same pattern whenever a problem asks “how many elements of this collection belong to that mathematical set” – from primes to perfect squares to triangular numbers, the shape is identical.

Try adapting the code to return the actual Fibonacci values that appeared, or to work on a long[] instead of an int[], and you will cement the pattern. You can learn more array algorithms here: Arrays on Daily Java Concept.