Suma de números en el K-ésimo nivel de un triángulo de Fibonacci

Dado un número K , la tarea es encontrar la suma de números en el K-ésimo nivel del triángulo de Fibonacci .
Ejemplos: 
 

Input: K = 3
Output: 10
Explanation: 
Fibonacci triangle till level 3:
  0
 1 1
2 3 5
Sum at 3rd level = 2 + 3 + 5 = 10

Input: K = 2
Output: 2
Explanation: 
Fibonacci triangle till level 3:
  0
 1 1
Sum at 3rd level = 1 + 1 = 2 

Acercarse: 

1. Hasta el nivel K, es decir, desde el nivel [1, K-1], el recuento de números de Fibonacci ya utilizados se puede calcular como: 
    

cnt = N(Level 1) + N(Level 2)
      + N(Level 3) + ... 
      + N(Level K-1)
    = 1 + 2 + 3 + ... + (K-1)
    = K*(K-1)/2

1.  
2. Además, sabemos que el K-ésimo nivel contendrá K números de Fibonacci.
3. Por lo tanto, podemos encontrar los números en el nivel K como números de Fibonacci en el rango [(cnt + 1), (cnt + 1 + K)] .
4. Podemos encontrar la suma de los números de Fibonacci en un rango en tiempo O(1) usando la fórmula de Binet.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation to find
// the Sum of numbers in the
// Kth level of a Fibonacci triangle
 
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
 
// Function to return
// the nth Fibonacci number
int fib(int n)
{
    double phi = (1 + sqrt(5)) / 2;
    return round(pow(phi, n) / sqrt(5));
}
 
// Function to return
// the required sum of the array
int calculateSum(int l, int r)
{
 
    // Using our deduced result
    int sum = fib(r + 2) - fib(l + 1);
 
    return sum;
}
 
// Function to return the sum of
// fibonacci in the Kth array
int sumFibonacci(int k)
{
    // Count of fibonacci which are in
    // the arrays from 1 to k - 1
    int l = (k * (k - 1)) / 2;
    int r = l + k;
 
    int sum = calculateSum(l, r - 1);
 
    return sum;
}
 
// Driver code
int main()
{
 
    int k = 3;
 
    cout << sumFibonacci(k);
 
    return 0;
}

// Java implementation to find
// the Sum of numbers in the
// Kth level of a Fibonacci triangle
import java.util.*;
 
class GFG
{
 
// Function to return
// the nth Fibonacci number
static int fib(int n)
{
    double phi = (1 + Math.sqrt(5)) / 2;
    return (int)Math.round(Math.pow(phi, n) / Math.sqrt(5));
}
 
// Function to return
// the required sum of the array
static int calculateSum(int l, int r)
{
 
    // Using our deduced result
    int sum = fib(r + 2) - fib(l + 1);
 
    return sum;
}
 
// Function to return the sum of
// fibonacci in the Kth array
static int sumFibonacci(int k)
{
    // Count of fibonacci which are in
    // the arrays from 1 to k - 1
    int l = (k * (k - 1)) / 2;
    int r = l + k;
 
    int sum = calculateSum(l, r - 1);
 
    return sum;
}
 
// Driver code
public static void main(String args[])
{
 
    int k = 3;
 
    System.out.println(sumFibonacci(k));
}
}
 
// This code is contributed by AbhiThakur

# Python3 implementation to find
# the Sum of numbers in the
# Kth level of a Fibonacci triangle
 
import math
MAX = 1000000
 
# Function to return
# the nth Fibonacci number
def fib(n):
 
    phi = (1 + math.sqrt(5)) / 2
    return round(pow(phi, n) / math.sqrt(5))
  
 
# Function to return
# the required sum of the array
def calculateSum(l, r):
 
    # Using our deduced result
    sum = fib(r + 2) - fib(l + 1)
 
    return sum
 
# Function to return the sum of
# fibonacci in the Kth array
def sumFibonacci(k) :
    # Count of fibonacci which are in
    # the arrays from 1 to k - 1
    l = (k * (k - 1)) / 2
    r = l + k
 
    sum = calculateSum(l, r - 1)
 
    return sum
 
# Driver code
k = 3
 
print(sumFibonacci(k))
 
# This code is contributed by Sanjit_Prasad

// C# implementation to find
// the Sum of numbers in the
// Kth level of a Fibonacci triangle
using System;
 
class GFG 
{
   
// Function to return
// the nth Fibonacci number
static int fib(int n)
{
    double phi = (1 + Math.Sqrt(5)) / 2;
    return (int)Math.Round(Math.Pow(phi, n) / Math.Sqrt(5));
}
  
// Function to return
// the required sum of the array
static int calculateSum(int l, int r)
{
  
    // Using our deduced result
    int sum = fib(r + 2) - fib(l + 1);
  
    return sum;
}
  
// Function to return the sum of
// fibonacci in the Kth array
static int sumFibonacci(int k)
{
    // Count of fibonacci which are in
    // the arrays from 1 to k - 1
    int l = (k * (k - 1)) / 2;
    int r = l + k;
  
    int sum = calculateSum(l, r - 1);
  
    return sum;
}
  
// Driver code
public static void Main() 
{ 
  
    int k = 3;
  
    Console.Write(sumFibonacci(k));
}
}
 
// This code is contributed by mohit kumar 29

<script>
  
// Javascript implementation to find
// the Sum of numbers in the
// Kth level of a Fibonacci triangle
  
    // Function to return
    // the nth Fibonacci number
    function fib(n) {
        var phi = (1 + Math.sqrt(5)) / 2;
        return parseInt( Math.round
        (Math.pow(phi, n) / Math.sqrt(5)));
    }
  
    // Function to return
    // the required sum of the array
    function calculateSum(l , r) {
  
        // Using our deduced result
        var sum = fib(r + 2) - fib(l + 1);
  
        return sum;
    }
  
    // Function to return the sum of
    // fibonacci in the Kth array
    function sumFibonacci(k)
    {
        // Count of fibonacci which are in
        // the arrays from 1 to k - 1
        var l = (k * (k - 1)) / 2;
        var r = l + k;
  
        var sum = calculateSum(l, r - 1);
  
        return sum;
    }
  
    // Driver code
      
  
        var k = 3;
  
        document.write(sumFibonacci(k));
  
// This code is contributed by todaysgaurav
  
</script>

10

Complejidad de tiempo: O((log n) + (n ^1/2 ))

Espacio Auxiliar: O(1)