Vdopia Interview Question
Software Engineer / DevelopersCountry: 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