## Vdopia Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**Phone Interview

```
public int createFibo(int a, int b, List<Integer> fibo)
{
int count =0;
int num = a;
int bitsum=0;
while(num!=0)
{
bitsum =+ numToBitSum(num);
num = num/10
}
while(a <= b)
{
if(fibo.contains(bitsum))
{
count++;
}
a++;
}
return count;
}
public int numToBitSum(int num)
{
if(num!=0)
{
return num%10;
}
```

}

For input a = 173, b=10000003210005, my answer is 1246892717288.

Look at my implementation first, ignore below explanation.

Suppose the input is 64 bits.

We can see that there are only 9 Fibonacci numbers less than 64: 1, 2, 3, 5, 8, 13, 21, 34, 55.

My solution uses combinatorial formula.

This can be efficiently computed using "Pascal Triangle" without overflow.

The hard part is how to count the answer for all numbers that less than a number Y.

Lets take a concrete example:

Y = 106 = 1101010 in binary; N = 7 bits.

R = 3

Consider numbers in following forms Y1, Y2, Y3, Y4:

Then, numbers in forms of Y1, Y2, Y3, Y4 have 3 properties:

1. All are less than Y;

2. They are non-overlap;

3. They cover all possible numbers less than Y.

Thus, now I have to count how many numbers in each form that satisfy the requirement

For Y1: there are C(6,3) such numbers;

For Y2: there are C(5,2) such numbers;

For Y3: there are C(3,1) such numbers;

For Y4: There are C(1,0) such numbers;

The final answer is: there are C(6,3) + C(5,2) + C(3,1) + C(1,0) = 34 numbers that less than 106 and have bit sum of 3.

To answer the original question, we have to do for all 9 Fibonacci numbers.

And a trick:

[a,b] = [0, b+1) - [0,a)

EDITED:

Time complexity: O(log b * log log b)

Reasons:

Number of bits in the number b is n = log b

Number of Fibonacci numbers that are less than n is O(log n).

CODE:

- ninhnnsoc May 12, 2014