Frequency of character B in Fibonacci string and time limit exceed error

Question

Consider the character string generated by the following rule:

• F[0] = "A"
• F[1] = "B"
• ...
• F[n] = F[n-1] + F[n-2] with n > 1

Given two positive integers n and k. Let's count the number of characters 'B' in the first k positions of string F[n].

I came up with this idea and got time limit exceeded error:

public class Solution {
    public static long[] F = new long[50];
    public static Scanner input = new Scanner(System.in);

    public static long count(int n, long k) {
        if (n == 0 || k == 0) return 0;
        else if (n == 1) return 1;
        else {
            if (k > F[n - 1]) return count(n - 1, F[n - 1]) + count(n - 2, k - F[n - 1]);
            else return count(n - 1, k);
        }
    }

    public static void main(String[] args) {
        F[0] = 1; F[1] = 1;
        for (int i = 2; i < 46; i++) F[i] = F[i - 2] + F[i - 1];
        int T = input.nextInt();
        while (T-- > 0) {
            int n = input.nextInt();
            long k = input.nextLong();
            System.out.println(count(n, k));
        }
    }
}

Can someone help me to improve time complexity? Seems my solution has O(n^2) time complexity.

Test case for this question:

Input	Output
4
0 1	0
1 1	1
3 2	1
7 7	4

Answer 1

For clarity, define Fib(n) to be the Fibonacci sequence where Fib(0) = Fib(1) = 1, and Fib(n+2) = Fib(n+1) + Fib(n).

Note that F[n] has Fib(n) characters, with Fib(n-1) of them being Bs.

Let C(n, k) be the number of B's in the first k characters of F[n].

The base cases are obvious

C(0, k) = 0
C(n, k) = 0 if k<=0
C(1, 1) = 1
C(2, k) = 1

In general:

C(n, k) = C(n-1, k)                         if k <= Fib(n-1)
        = Fib(n-2) + C(n-1, k - Fib(n-1))   otherwise

This is the observation that F[n] = F[n-1] + F[n-2] and k lies in either the first part or the second. The first part has Fib(n-1) characters of which Fib(n-2) of them are B's.

If you precompute the Fibonacci numbers from 0 to n, then you can compute C(n, k) in O(n) arithmetic operations.

You tagged java, but here's a python solution including test cases:

def C(n, k):
    if n == 0: return 0
    total = 0
    fib = [1, 1]
    while len(fib) <= n and fib[-1] <= k:
        fib.append(fib[-1] + fib[-2])
    n = min(n, len(fib) - 1)
    while True:
        if n <= 2:
            return total + 1
        elif k <= fib[n-1]:
            n -= 1
        else:
            total += fib[n-2]
            k -= fib[n-1]
            n -= 1

tcs = [
    ([0, 1], 0),
    ([1, 1], 1),
    ([3, 2], 1),
    ([7, 7], 4)
]

for (n, k), want in tcs:
    got = C(n, k)
    if got != want:
        print('C(%d, %d) = %d, want %d' % (n, k, got, want))

This includes an optimization which reduces n so that initially k > Fib(n-1). This makes the code O(min(n, log(k))) arithmetic operations.