CareerCup

public class GetFibonacciNumbers {
    public static void main(String[] args) {
        int[] given = new int[] {3, 6, 7, 9, 2};
        int[] output = getFibonnaciNumbers(given);
        printArray("given", given);
        printArray("output", output);
    }

    private static void printArray(String name, int[] given) {
        StringBuilder sb = new StringBuilder(name);
        sb.append(": ");
        for(int i=0; i < given.length; i++) {
            if (i > 0)
                sb.append(", ");
            sb.append(given[i]);
        }
        System.out.println(sb);
    }

    private static int[] getFibonnaciNumbers(int[] given) {
        int[] output = new int[given.length];
        int index = 0;
        for(int x : given) {
            int nearestFib = getNearestFibonacciNumber(x);
            if (x == nearestFib)
                output[index++] = x;
        }
        return output;
    }

    private static int getNearestFibonacciNumber(int given) {
        int fN = 1;
        int fNPrev = 1;
        while(fN < given) {
            int temp = fN;
            fN = fN + fNPrev;
            fNPrev = temp;
        }
        System.out.println("Neartest to " + given + " is " + fN);
        return fN;
    }
}

We keep cache of calculated Fib numbers and run through the array. If next elem in array greater then last calculated in cache - we calc all fib numbers till next and check if it's in cache

public static List<int> getFibNumbers(int[] nums)
        {
            int lastFib = 1;
            int nextFib = 1;
            int temp;
            HashSet<int> cache = new HashSet<int>();
            cache.Add(1);
            var result = new List<int>();
            foreach (var item in nums)
            {
                while (item > nextFib)
                {
                    temp = lastFib;
                    lastFib = nextFib;
                    nextFib = temp + lastFib;
                    cache.Add(nextFib);
                }
                if (cache.Contains(item)) result.Add(item);
            }
            return result;
        }

#!/usr/bin/python
import math
def isPerfectSqr(n):
x = int(math.sqrt(n))
return x*x == n

def isFibonacci(num):
#5n**2+4 or 5n**2-4 should be true
first = 5*num**2 + 4
second = 5*num**2 - 4
if (isPerfectSqr(first) or isPerfectSqr(second)):
return True
else:
return False

def fibonacci(input_list):
result = []
for num in input_list:
if isFibonacci(num):
result.append(num)
return result

if __name__ =='__main__':
input_list = [4, 2, 8, 5, 20, 1, 40, 13, 23]
#output: [2, 5, 1, 8, 13]

print fibonacci(input_list)

There are two standard version of Fibonacci series -
1) 0,1,1,2,3,5,8....
2) 1,1,2,3,5,8.....

We will use first in our problem.
1- Find max in the array - O(n)
*max number will be used to generate Fibonacci series to the number max. In given example the max is 40.
2- Generate Fibonacci to the number max and store it in hashset/hashmap. in our eg. the fibset will be (0,1,2,3,5,8,13,21,34)
3- Traverse array again if the number is present in hashset/hashmap then add it to the list.
4- Return list

Time complexity - O(n)

public class FibonacciSubset {

	private static ArrayList<Integer> findNumbers(int[] ar){
		
		int max = findMax(ar);
		ArrayList<Integer> list = new ArrayList<>();
		Set<Integer>  fibset = fiboNumbers(max);
		for(int i=0;i<ar.length;i++){
			if(fibset.contains(ar[i])){
				list.add(ar[i]);
			}
		}
		return list;
	}
	
	
	private static int findMax(int[] ar) {
		int max= ar[0];
		for(int i=1;i<ar.length;i++){
			max = max > ar[i] ? max : ar[i];
		}
		return max;
	}

	private static Set<Integer> fiboNumbers(int max) {
		HashSet<Integer> fibset = new HashSet<>();
		fibset.add(0);
		fibset.add(1);
		int f = 0,s =1;
		int res = f + s;
		while(res < max){
			fibset.add(res);
			f = s;
			s = res;
			res = f + s;
		}
		return fibset;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] ar = {4,2,8,5,20,1,40,13,23};
		ArrayList<Integer> list = findNumbers(ar);
		
		for(int i=0;i<list.size();i++){
			System.out.print(list.get(i) + " ");
		}
	}

}

/* 
Showing Idiomatic ZoomBA 
*/
input = [4,2,8,5,20,1,40,13,23] 
#(m,M) = minmax(input)
fib = seq ( 0, 1 ) -> { $.item[-1] + $.item[-2 ] } 
while ( fib.next <= M );
result = input & fib.history
println(result)

Now the result:

➜  wiki git:(master) ✗ zmb tmp.zm
[ 1,2,5,8,13 ]
➜  wiki git:(master) ✗

Solution in Python

from itertools import takewhile

def fib():
    a = 0; b = 1
    while True:
        yield a
        temp = a
        a = b
        b += temp
        

def getFibNumbers(nums):
    m = max(nums)
    s = set(takewhile(lambda x: x < m,
                      fib()))
    return s.intersection(nums)

Using a Math property to check is a number is Fibonacci, O(n)
A number is fibbonaci if (5*n2 + 4) or (5*n2 – 4) is a perfect square

public static List<int> GetFibonacciSequence(int[] a)
{
	var list = new List<int>();
	
	if (a == null)
		return list;
	
	foreach (var n in a)
		if (IsFibonacci(n))
			list.Add(n);
		
	return list;
}

//A number is fibbonaci if (5*n2 + 4) or (5*n2 – 4) is a perfect square
public static bool IsFibonacci(int n)
{
	int f = (5 * n * n);
	int f1 = f + 4;
	
	if (IsPerfectSquare(f1))
		return true;
	
	int f2 = f - 4;
	if (IsPerfectSquare(f2))
		return true;
	
	return false;
}

public static bool IsPerfectSquare(int n)
{
	int sqrt = (int)Math.Sqrt(n);
	return sqrt * sqrt == n;
}

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
class Program
{
static bool isfib(int n)
{
int x = 5 * n * n + 4;
int y = 5 * n * n - 4;
int sx = (int)Math.Sqrt(x);
int sy = (int)Math.Sqrt(y);
if (sx * sx == x)
return true;
else if (sy * sy == y)
return true;
else
return false;
}
static void Main(string[] args)
{
int []arr = { 4, 2, 8, 5, 20, 1, 40, 13, 23 };
for (int i = 0; i < arr.Length; i++)
{
if (isfib(arr[i]))
Console.WriteLine(arr[i]);
}
Console.ReadKey();
}
}
}

1. store the input numbers in a Map<Integer,Boolean> initially assigned to false.
2. find the maxNum present in the input array
3. find all the fibonacci numbers until the maxNum. If any of the intermediate fibonacci numbers are present in the map, assign a true value.
4. traverse through the input array and add the numbers that have true in the map.

public static List<Integer> getFibNumbers(int[] nums){
	List<Integer> result = new LinkedList<>();
	if(nums==null || nums.length==0)
		return result;

	Map<Integer,Boolean> fiboMap = new HashMap<>();
	int maxNum=Integer.MIN_VALUE;
	for(int num: nums){
		fiboMap.put(num, false);
		maxNum = Math.max(maxNum, num);
	}
	findFibo(maxNum, fiboMap);
	for(int num: nums){
		if(fiboMap.get(num)){
			result.add(num);
		}
	}
	return result;
}
private static void findFibo(int maxNum, Map<Integer, Boolean> fiboMap){
	int dp1=0, dp2=1, dp3=0;
	
	while(dp3<maxNum){
		dp3=dp1+dp2;
		dp1=dp2;
		dp2=dp3;
		if(fiboMap.containsKey(dp3)){
			fiboMap.put(dp3,true);
		}
	}
}