@@ -3,22 +3,23 @@
3  *
4  * For n = 30, the expected result is 1,346,268.
5  *
6- * Uses iterative approach: O(n) time, O(1) space.
7- * Computes fibonacci values and accumulates sum in a single pass.
6+ * Uses the identity: sum(F(0)..F(n-1)) = F(n+1) - 1
7+ * Combined with fast doubling for O(log n) time.
8  */
9 export function sumFibonacci(n: number): number {
10   if (n <= 0) return 0;
11+  const [a] = fastDoubling(n + 1);
12+  return a - 1;
13+}
14 
12-  let sum = 0;
13-  let a = 0;
14-  let b = 1;
15-
16-  for (let i = 0; i < n; i++) {
17-    sum += a;
18-    const next = a + b;
19-    a = b;
20-    b = next;
15+// Returns [F(n), F(n+1)] using fast doubling in O(log n) time
16+function fastDoubling(n: number): [number, number] {
17+  if (n === 0) return [0, 1];
18+  const [a, b] = fastDoubling(n >> 1);
19+  const c = a * (2 * b - a);
20+  const d = a * a + b * b;
21+  if (n & 1) {
22+    return [d, c + d];
23   }
22-
23-  return sum;
24+  return [c, d];
25 }