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 some one help me to improve time complexity? Seems my solution has O(n^2) time complexity.

Test case for this question:

CodePudding user response：

There seems to be a pattern related to Fibonacci numbers:

A
B
AB 1   1 (A count   B count)
BAB 1   2
ABBAB 2   3
BABABBAB 3   5
ABBABBABABBAB 5   8
      ^ k = 7
     BABABBAB 3   5
      ^ k = 2 (result = 3)
     BAB 1   2
      ^ k = 2 (result = 4)
     AB 1   1
     ^ k = 1 = A (result = 4)

Let g(l, r, k) represent the count of Bs in the first k positions of Fib[n] = l r. Then:

g(l, r, k):
  if (1, 1) == (l, r):
    return 1 if k == 2 else 0
  if (1, 2) == (l, r):
    return 1 if k < 3 else 2
  ll, rl = getFibSummands(l)
  lr, rr = getFibSummands(r)
  if k > l:
    return rl   g(lr, rr, k - l)
  return g(ll, rl, k)

This answer above may have misinterpreted the starting order of concatenation, which possibly should be BA, in which case, we would need to reverse l, r.

A
B
BA 1   1 (B count   A count)
BAB 2   1 
BABBA 3   2
BABBABAB 5   3
BABBABABBABBA 8   5
      ^ k = 7
BABBABAB
      ^ k = 7
     BAB
      ^ k = 2 (result = 3)
     BA
      ^ k = 2
      A
      ^ k = 1 (result = 4)

g(l, r, k):
  if (1, 1) == (l, r):
    return 1 if k == 2 else 0
  if (2, 1) == (l, r):
    return 1 if k < 3 else 2
  ll, rl = getFibSummands(l)
  lr, rr = getFibSummands(r)
  if k > l:
    return ll   g(lr, rr, k - l)
  return g(ll, rl, k)

CodePudding user response：

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.