## Interview Question

SDE-2s**Country:**Russia

c++, fibonacci, O(log n)

```
typedef unsigned long long UINT64;
UINT64 fibonacci(int n) {
int k;
UINT64 a, b, ret;
if (n <= 2) return 1;
k = n / 2;
a = fibonacci(k + 1);
b = fibonacci(k);
if (n % 2 == 1) ret = a * a + b * b;
else ret = b * (2 * a - b);
return ret;
}
UINT64 casesOfReading(int n) {
return fibonacci(n + 1);
}
```

the question is just to ask a fibonacci sequence actually

}

- Scott November 16, 2015