CareerCup

We could use Binet's formula for finding the n- th fibonachi number. Actually Fibonachi numbers are very famous numbers because of their golden rule ratio. O(1) time and memory complexity

long findFibCount(long n) {	 
	 if (n == 0)
		 return 0;
	 if (n == 1)
		 return 1;
         double sqrtFive = Math.sqrt(5);
	 double fi = (1.0 + sqrtFive )/2.0;
	 int index =  (int) (Math.log(n *sqrtFive  +0.5) / Math.log (fi)); 	 
	 int res = (int)((Math.pow(fi,index) / sqrtFive ) +0.5);
	 if (res != n) {
		 index +=1;
	 }
	 return index;
	 
 }

public static int countValuesofFibonacci(int x){

        if ( x <= 0){
            return 0;
        }
        if ( x== 1){
            return 1;
        }
        int a = 0;
        int b = 1;
        int count = 2;
        int temp;
        while (a+b < x){
            count += 1;
            temp = b;
            b = a+b;
            a = temp;
        }

        return count;

    }

This takes appx. O (lgn) complexity.

brute force approach works here with approximate complexity "log n", so all the tricks are unneeded here.
Proof:
1) Given n = 1.000.
Brute force will find solution in 17 steps.
2) Given n = 1.000.000.
Brute force will find solution in 31 steps.
3) Given n = 1.000.000.000.
Brute force will find solution in 45 steps.
etc.

You can expand fib into a tail recursive function, and then from that into a simple iterative loop. From there it's pretty straightforward. O(n).

public static int fibTermsBeforeN(int n)
    {
        int val = 0;
        int prev = 1;
        int count = 0;

        for(; val < n; ++count)
        {
            val = val + prev;
            prev = val - prev;
        }

        return count;
    }

// ZoomBA, showcasing iterator object creation.
// This is infinite iterator. 
def FibGen :{ previous : [ 0, 1] , 
      $next : def(){
      cur = $.previous[0] + $.previous[1]
      $.previous[0] = $.previous[1]
      $.previous[1] = cur 
    } 
}
fg = new ( FibGen )
n = 6 
count = lfold ( fg, 2 ) -> { break( $.o >= n ) ; $.p += 1 }
println( count )

First thing is definitely ask about n, how large it can be.
first solution is to pregenerate fibbonachi numbers up to maximum value of n, the do binary search over it. O(N) - memory, O(logN) complexity

second solution is to binary search on n-th fibbonachi number. n-th fibbonachi can be found in O(logN) with power exponentiation so the complexity including binary search would be O(logN * logN)

the question remains: can this be done faster than O(logn)?

It's just a basic addition of 2 numbers given the proper input and an upper limit.

void findFib(int n)
  {
          int fibNum = 0, prevFibNum = 1, count = 1;
          while (fibNum < n) {
                  printf("Fibonacci number %d is:  %d\n", count, fibNum);
                  fibNum += prevFibNum;
                  prevFibNum = fibNum-prevFibNum;
                  count++;
         }
 }

public int countFiboLessThan(int n)
{
	if(n<=0)
	{
		return 0;
	}
	int a=0;
	int b=1;
	int count=2;
	while(b<n)
	{
		int tmp=a;
		a=b;
		b=b+tmp;
		count++;
		
	}
	return count-1;
}

Use fast exponential to calculate Fib(n), break when Fib(n) > input, climb down to Fib(n/2) and multiply until Fib(n/2 + x) < input. Return count.

#include <iostream>
#include <vector>

using namespace std;

class FiboExist{

public :
  
  
int fibo(int n){
    
    int ans = 0;
    
    if(n <= 1){
	ans = n;
    }else{
  	int a = 0, b = 1;
	ans=1;
   	while(b < n){
    	   int c = a;
	   a = b;
	   b = a+c;
	   ans++;
        }
    }
  
    return ans;
  }

};


int main(){
   
   FiboExist fb;
   cout<<fb.fibo(3)<<endl;
   
   
   return 0;
}

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
Ideone fibtest = new Ideone();
System.out.println(fibtest.fibCount(2));
}

public int fibCount(int target) {

if (target == 0) return 0;
if (target == 1) return 1;

ArrayList<Integer> fibs = new ArrayList<>();

fibs.add(0);
fibs.add(1);
int count = 2;


while (fibs.get(count-1) < target) {
fibs.add(fibs.get(count-1) + fibs.get(count-2));
if (fibs.get(count) >= target) return count;
++count;
}
return count;
}
}

#include<stdio.h>

int main()
{
int count=0;
int n;
printf("enter the number:=> ");
scanf("%d",&n);
int i,fibo=0;
int previous2=1,previous1=-1;

for(i=0;fibo<n;i++)
{

fibo=previous1+previous2;
if(fibo<=n)
{
count++;
printf("%d ",fibo);
}
else
break;
previous1=previous2;
previous2=fibo;

}
printf("\n");
printf(" the no of term in fibonacii series is :=>:%d",count);
return 0;
}

#include <iostream>
#include <vector>

using namespace std;

vector<int> fibo(int range);

int main()
{
vector<int> sum;
int range;
cout<<"Enter the number range: "<<endl;
cin>>range;
sum = fibo(range);
cout<<"Output : ";
for(unsigned int i=0 ; i<sum.size() ; i++){
cout<<sum[i]<<" ";
}

return 0;
}

vector<int> fibo(int range) {

vector<int> temp;
temp.push_back(0);
temp.push_back(1);
int i=0;
while(temp.size() < range) {
temp.push_back(temp[i+1]+temp[i]);
i++;
}
return temp;
}

how about this solution

#include <stdio.h>
#include <stdlib.h>

#define SIZE 6
int fib(int n, int arr[]){
	if (n == 0 || n == 1){
		arr[n] = n;
		return n;
	}
	return arr[n] = (fib(n - 1, arr) + fib(n - 2, arr));
}
int main(){
	int *arr = (int*)calloc(sizeof(int)* SIZE, 1);
	fib(SIZE, arr);
	for (int i = 0; i < SIZE; i++)
		printf("%d ", arr[i]);
	return 0;
}

def num_fib_under_n(n):
	if n <= 1:
		return n
	count = 2
	a, b = 0, 1
	while True:
		a, b = b, a+b
		if (b > n):
			return count
		count += 1

print(num_fib_under_n(6))