Dada una array de n elementos, la tarea es encontrar la suma de Fibonacci de un subconjunto de la array donde cada elemento del subconjunto <= k.
Precisamente, encuentre F(A i1 ) + F(A i2 ) + F(A i3 ) + … + F(A ix )) , donde (A i1 , A i2 , …, A ix ) <= K y 1 <= (i 1 , i 2 , …, i x ) <= n. Aquí, F(i) es el i- ésimo número de Fibonacci
Ejemplos:
Input : arr = {1, 2, 3, 4, 2, 7}
Query 1 : K = 2
Query 2 : K = 6
Output : 3
8
Explicación:
en la consulta 1 , el subconjunto {1, 2, 2} es un subconjunto en el que todos los elementos del subconjunto son <= k, es decir, <= 2 en este caso. La suma de Fibonacci del subconjunto = F(1) + F(2) + F(2) = 1 + 1 + 1 = 3 En
la consulta 2 , el subconjunto {1, 2, 3, 4, 2} es uno de esos subconjuntos donde todos los elementos del subconjunto son <= k, es decir, <= 6 en este caso. La suma de Fibonacci del subconjunto = F(1) + F(2) + F(3) + F(4) + F(2) = 1 + 1 + 2 + 3 + 1 = 8 Resuelve esto usando dos técnicas de consulta
diferentes , a saber:
1) Consulta en línea,
2) Consulta fuera de línea
En ambos métodos, el único paso común es la generación del enésimoNúmero de Fibonacci. Para obtener una técnica eficiente para generar el n -ésimo número de Fibonacci usando este .
Este método de generar los números de Fibonacci es común a ambas técnicas de consulta. Ahora, mire cómo usar estos números de Fibonacci que se generan usando cada una de estas dos técnicas.
Método 1 (Consultas en línea):
en esta técnica, procesa las consultas a medida que llegan. En primer lugar, ordene la array en orden creciente. Después de obtener una consulta para una k en particular, use la búsqueda binaria en esta array ordenada para encontrar el último índice donde el valor de la array es & <= k. Llamemos a esta posición x.
Ahora, dado que la array está ordenada,
For all i <= x, a[i] <= x i.e a[i] <= a[x] for all i ∈ [1, x]
Entonces, el subconjunto en el que enfocarse es A 1 , A 2 , A 3 , ….A x en la array ordenada A, y la suma de Fibonacci es: F(A 1 )+F(A 2 )+F(A 3 )+ …+F(A x )
Use arreglos de suma de prefijos para encontrar de manera eficiente la suma del subconjunto A 1 , A 2 , A 3 , ….A x .
Si prefixFibSum[i] almacena la suma de Fibonacci hasta el i- ésimo índice de la array ordenada A, entonces, la suma de Fibonacci del subconjunto de la array de 1 a x, es prefixFibSum[x]
Por lo tanto, la suma de Fibonacci del subconjunto[1…x ] = prefijoFibSuma[x], prefixFibSum[x] se puede calcular de la siguiente manera:
prefixFibSum[x] = prefixFibSum[x – 1] + A[x] el número de Fibonacci, donde A[x] es el elemento de array en el índice x de la array .
C++
// C++ program to find fibonacci sum of
// subarray where all elements <= k
#include <bits/stdc++.h>
using namespace std;
// Helper function that multiplies 2 matrices
// F and M of size 2*2, and puts the multiplication
// result back to F[][]
void multiply(int F[2][2], int M[2][2])
{
int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
/* Helper function that calculates F[][]
raise to the power n and puts the
result in F[][] */
void power(int F[2][2], int n)
{
int i;
int M[2][2] = { { 1, 1 }, { 1, 0 } };
// n - 1 times multiply the
// matrix to {{1, 0}, {0, 1}}
for (i = 2; i <= n; i++)
multiply(F, M);
}
// Returns the nth fibonacci number
int fib(int n)
{
int F[2][2] = { { 1, 1 }, { 1, 0 } };
if (n == 0)
return 0;
power(F, n - 1);
return F[0][0];
}
int findLessThanK(int arr[], int n, int k)
{
// find first index which is > k
// using lower_bound
return (lower_bound(arr, arr + n, k + 1)
- arr);
}
// Function to build Prefix Fibonacci Sum
int* buildPrefixFibonacciSum(int arr[], int n)
{
// Allocate memory to prefix
// fibonacci sum array
int* prefixFibSum = new int[n];
// Traverse the array from 0 to n - 1,
// when at the ith index then we calculate
// the a[i]th fibonacci number and calculate
// the fibonacci sum till the ith index as
// the sum of fibonacci sum till index i - 1
// and the a[i]th fibonacci number
for (int i = 0; i < n; i++)
{
int currFibNumber = fib(arr[i]);
if (i == 0) {
prefixFibSum[i] = currFibNumber;
}
else {
prefixFibSum[i] = prefixFibSum[i - 1]
+ currFibNumber;
}
}
return prefixFibSum;
}
// Return the answer for each query
int processQuery(int arr[], int prefixFibSum[],
int n, int k)
{
// index stores the index till where
// the array elements are less than k
int lessThanIndex = findLessThanK(arr, n, k);
if (lessThanIndex == 0)
return 0;
return prefixFibSum[lessThanIndex - 1];
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 2, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
// sort the array arr
sort(arr, arr + n);
// Build the prefix fibonacci sum array
int* prefixFibSum =
buildPrefixFibonacciSum(arr, n);
// query array stores q queries
int query[] = { 2, 6 };
int q = sizeof(query) / sizeof(query[0]);
for (int i = 0; i < q; i++) {
int k = query[i];
int ans =
processQuery(arr, prefixFibSum, n, k);
cout << "Query " << i + 1 << " : "
<< ans << endl;
}
return 0;
}
Java
// Java program to find fibonacci sum of
// subarray where all elements <= k
import java.util.*;
class GFG
{
// Helper function that multiplies 2 matrices
// F and M of size 2*2, and puts the multiplication
// result back to F[][]
static void multiply(int[][] F, int[][] M)
{
int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
/*
* Helper function that calculates F[][]
raise to the power n and puts the
* result in F[][]
*/
static void power(int[][] F, int n)
{
int i;
int[][] M = { { 1, 1 }, { 1, 0 } };
// n - 1 times multiply the
// matrix to {{1, 0}, {0, 1}}
for (i = 2; i <= n; i++)
multiply(F, M);
}
// Returns the nth fibonacci number
static int fib(int n)
{
int[][] F = { { 1, 1 }, { 1, 0 } };
if (n == 0)
return 0;
power(F, n - 1);
return F[0][0];
}
static int findLessThanK(int arr[], int n, int k)
{
// find first index which is > k
// using lower_bound
return (lower_bound(arr, 0, n, k + 1));
}
static int lower_bound(int[] a, int low,
int high, int element)
{
while (low < high)
{
int middle = low + (high - low) / 2;
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
// Function to build Prefix Fibonacci Sum
static int[] buildPrefixFibonacciSum(int arr[], int n)
{
// Allocate memory to prefix
// fibonacci sum array
int[] prefixFibSum = new int[n];
// Traverse the array from 0 to n - 1,
// when at the ith index then we calculate
// the a[i]th fibonacci number and calculate
// the fibonacci sum till the ith index as
// the sum of fibonacci sum till index i - 1
// and the a[i]th fibonacci number
for (int i = 0; i < n; i++)
{
int currFibNumber = fib(arr[i]);
if (i == 0)
{
prefixFibSum[i] = currFibNumber;
}
else
{
prefixFibSum[i] = prefixFibSum[i - 1] +
currFibNumber;
}
}
return prefixFibSum;
}
// Return the answer for each query
static int processQuery(int arr[], int prefixFibSum[],
int n, int k)
{
// index stores the index till where
// the array elements are less than k
int lessThanIndex = findLessThanK(arr, n, k);
if (lessThanIndex == 0)
return 0;
return prefixFibSum[lessThanIndex - 1];
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 2, 7 };
int n = arr.length;
// sort the array arr
Arrays.sort(arr);
// Build the prefix fibonacci sum array
int[] prefixFibSum = buildPrefixFibonacciSum(arr, n);
// query array stores q queries
int query[] = { 2, 6 };
int q = query.length;
for (int i = 0; i < q; i++)
{
int k = query[i];
int ans = processQuery(arr, prefixFibSum, n, k);
System.out.print("Query " + (i + 1) + " : " + ans + "\n");
}
}
}
// This code is contributed by Rajput-Ji
C#
// C# program to find fibonacci sum of
// subarray where all elements <= k
using System;
class GFG
{
// Helper function that multiplies 2 matrices
// F and M of size 2*2, and puts the multiplication
// result back to F[,]
static void multiply(int[,] F, int[,] M)
{
int x = F[0, 0] * M[0, 0] + F[0, 1] * M[1, 0];
int y = F[0, 0] * M[0, 1] + F[0, 1] * M[1, 1];
int z = F[1, 0] * M[0, 0] + F[1, 1] * M[1, 0];
int w = F[1, 0] * M[0, 1] + F[1, 1] * M[1, 1];
F[0, 0] = x;
F[0, 1] = y;
F[1, 0] = z;
F[1, 1] = w;
}
/*
* Helper function that calculates F[,]
raise to the power n and puts the
* result in F[,]
*/
static void power(int[,] F, int n)
{
int i;
int[,] M = { { 1, 1 }, { 1, 0 } };
// n - 1 times multiply the
// matrix to {{1, 0}, {0, 1}}
for (i = 2; i <= n; i++)
multiply(F, M);
}
// Returns the nth fibonacci number
static int fib(int n)
{
int[,] F = {{ 1, 1 }, { 1, 0 }};
if (n == 0)
return 0;
power(F, n - 1);
return F[0, 0];
}
static int findLessThanK(int []arr, int n, int k)
{
// find first index which is > k
// using lower_bound
return (lower_bound(arr, 0, n, k + 1));
}
static int lower_bound(int[] a, int low,
int high, int element)
{
while (low < high)
{
int middle = low + (high - low) / 2;
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
// Function to build Prefix Fibonacci Sum
static int[] buildPrefixFibonacciSum(int []arr, int n)
{
// Allocate memory to prefix
// fibonacci sum array
int[] prefixFibSum = new int[n];
// Traverse the array from 0 to n - 1,
// when at the ith index then we calculate
// the a[i]th fibonacci number and calculate
// the fibonacci sum till the ith index as
// the sum of fibonacci sum till index i - 1
// and the a[i]th fibonacci number
for (int i = 0; i < n; i++)
{
int currFibNumber = fib(arr[i]);
if (i == 0)
{
prefixFibSum[i] = currFibNumber;
}
else
{
prefixFibSum[i] = prefixFibSum[i - 1] +
currFibNumber;
}
}
return prefixFibSum;
}
// Return the answer for each query
static int processQuery(int []arr, int []prefixFibSum,
int n, int k)
{
// index stores the index till where
// the array elements are less than k
int lessThanIndex = findLessThanK(arr, n, k);
if (lessThanIndex == 0)
return 0;
return prefixFibSum[lessThanIndex - 1];
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 4, 2, 7 };
int n = arr.Length;
// sort the array arr
Array.Sort(arr);
// Build the prefix fibonacci sum array
int[] prefixFibSum = buildPrefixFibonacciSum(arr, n);
// query array stores q queries
int []query = {2, 6};
int q = query.Length;
for (int i = 0; i < q; i++)
{
int k = query[i];
int ans = processQuery(arr, prefixFibSum, n, k);
Console.Write("Query " + (i + 1) + " : " + ans + "\n");
}
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to find fibonacci sum of
// subarray where all elements <= k
// Helper function that multiplies 2 matrices
// F and M of size 2*2, and puts the multiplication
// result back to F[,]
function multiply(F, M) {
let x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
let y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
let z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
let w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
/*
* Helper function that calculates F[,]
raise to the power n and puts the
* result in F[,]
*/
function power(F, n) {
let i;
let M = [[1, 1], [1, 0]];
// n - 1 times multiply the
// matrix to {{1, 0}, {0, 1}}
for (i = 2; i <= n; i++)
multiply(F, M);
}
// Returns the nth fibonacci number
function fib(n) {
let F = [[1, 1], [1, 0]];
if (n == 0)
return 0;
power(F, n - 1);
return F[0][0];
}
function findLessThanK(arr, n, k) {
// find first index which is > k
// using lower_bound
return (lower_bound(arr, 0, n, k + 1));
}
function lower_bound(a, low, high, element) {
while (low < high) {
let middle = Math.floor(low + (high - low) / 2);
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
// Function to build Prefix Fibonacci Sum
function buildPrefixFibonacciSum(arr, n) {
// Allocate memory to prefix
// fibonacci sum array
let prefixFibSum = new Array(n);
// Traverse the array from 0 to n - 1,
// when at the ith index then we calculate
// the a[i]th fibonacci number and calculate
// the fibonacci sum till the ith index as
// the sum of fibonacci sum till index i - 1
// and the a[i]th fibonacci number
for (let i = 0; i < n; i++) {
let currFibNumber = fib(arr[i]);
if (i == 0) {
prefixFibSum[i] = currFibNumber;
}
else {
prefixFibSum[i] = prefixFibSum[i - 1] +
currFibNumber;
}
}
return prefixFibSum;
}
// Return the answer for each query
function processQuery(arr, prefixFibSum, n, k) {
// index stores the index till where
// the array elements are less than k
let lessThanIndex = findLessThanK(arr, n, k);
if (lessThanIndex == 0)
return 0;
return prefixFibSum[lessThanIndex - 1];
}
// Driver Code
let arr = [1, 2, 3, 4, 2, 7];
let n = arr.length;
// sort the array arr
arr.sort((a, b) => a - b);
// Build the prefix fibonacci sum array
let prefixFibSum = buildPrefixFibonacciSum(arr, n);
// query array stores q queries
let query = [2, 6];
let q = query.length;
for (let i = 0; i < q; i++) {
let k = query[i];
let ans = processQuery(arr, prefixFibSum, n, k);
document.write("Query " + (i + 1) + " : " + ans + "<br>");
}
// This code is contributed by gfgking
</script>
Python3
# Python3 program to find fibonacci sum of
# subarray where all elements <= k
from bisect import bisect
# Helper function that multiplies 2 matrices
# F and M of size 2*2, and puts the multiplication
# result back to F
def multiply(F, M):
x = F[0][0] * M[0][0] + F[0][1] * M[1][0]
y = F[0][0] * M[0][1] + F[0][1] * M[1][1]
z = F[1][0] * M[0][0] + F[1][1] * M[1][0]
w = F[1][0] * M[0][1] + F[1][1] * M[1][1]
F[0][0] = x
F[0][1] = y
F[1][0] = z
F[1][1] = w
# Helper function that calculates F
# raise to the power n and puts the
# result in F
def power(F, n):
M = [[1, 1], [1, 0]]
# n - 1 times multiply the
# matrix to [[1, 0], [0, 1]]
for i in range(1, n):
multiply(F, M)
# Returns the nth fibonacci number
def fib(n):
F = [[1, 1], [1, 0]]
if (n == 0):
return 0
power(F, n - 1)
return F[0][0]
def findLessThanK(arr, n, k):
# find first index which is > k
# using bisect
return (bisect(arr, k))
# Function to build Prefix Fibonacci Sum
def buildPrefixFibonacciSum(arr, n):
# Allocate memory to prefix
# fibonacci sum array
prefixFibSum = [0]*n
# Traverse the array from 0 to n - 1,
# when at the ith index then we calculate
# the a[i]th fibonacci number and calculate
# the fibonacci sum till the ith index as
# the sum of fibonacci sum till index i - 1
# and the a[i]th fibonacci number
for i in range(n):
currFibNumber = fib(arr[i])
if (i == 0):
prefixFibSum[i] = currFibNumber
else:
prefixFibSum[i] = prefixFibSum[i - 1] + currFibNumber
return prefixFibSum
# Return the answer for each query
def processQuery(arr, prefixFibSum, n, k):
# index stores the index till where
# the array elements are less than k
lessThanIndex = findLessThanK(arr, n, k)
if (lessThanIndex == 0):
return 0
return prefixFibSum[lessThanIndex - 1]
# Driver Code
if __name__ == '__main__':
arr = [1, 2, 3, 4, 2, 7]
n = len(arr)
# sort the array arr
arr.sort()
# Build the prefix fibonacci sum array
prefixFibSum = buildPrefixFibonacciSum(arr, n)
# query array stores q queries
query = [2, 6]
q = len(query)
for i in range(q):
k = query[i]
ans = processQuery(arr, prefixFibSum, n, k)
print("Query {} : {}".format(i+1, ans))
# This code is contributed by Amartya Ghosh
Producción:
Query 1 : 3 Query 2 : 8
Complejidad de tiempo: O(nlogn + qlogn)
Espacio auxiliar: O(N)
Método 2 (Consultas fuera de línea):
En consultas fuera de línea, almacene las consultas y calcule la respuesta para cada consulta en un orden específico y almacene y emita el resultado de las consultas en el orden original especificado.
Almacene cada consulta como un par de enteros donde el primer miembro del par es el parámetro de consulta K para esa consulta y el segundo miembro del par es el índice en el que se produce originalmente la consulta.
Por ejemplo, si las consultas son las siguientes:
consulta 1: K = 13;
consulta 2: K = 3;
consulta 3: K = 8;
luego, almacene la consulta 1 como donde 13 es el valor de K para esa consulta y 1 es el índice que especifica que es la primeraconsulta, de manera similar la consulta 2 y la consulta 3 se representan como y respectivamente.
Una vez, todas las consultas individuales se representan como pares de números enteros que clasifican la array de pares de consultas sobre la base de K de manera creciente.
Por ejemplo, las consultas anteriores después de ordenar se verán como {3 ,8 ,13}.
Idea detrás de la clasificación de consultas:
La idea principal detrás de la clasificación de consultas es que cuando hay elementos de un subconjunto que son menores que k para alguna consulta q i entonces para todas las consultas q j donde i < j y por lo tanto K i <= K j estos los elementos están presentes, por lo que si la array de elementos y las consultas (ordenadas por K) están ordenadas, mantenga dos punteros, uno en la array y el otro en la array de consultas.
yo, señalándometh índice de la array,
j, apuntando a j th índice de la array de consultas
Luego, considere el siguiente Pseudo Código:
while (i <= query[j].K) {
fibonacciSum = fibonacciSum + a[i]th Fibonacci number
i = i + 1
}
Entonces, mientras los elementos en el subconjunto son menores o iguales al primer miembro del par de consulta actual (es decir, K), continúe avanzando al siguiente elemento mientras agrega el número de Fibonacci requerido a la suma actual. Una vez que el elemento actual sea mayor que el parámetro K de la consulta actual, almacene el valor actual de sum en la array auxiliar denominada ans de tamaño q (es decir, número de consultas) en el índice señalado por el segundo miembro del par de la consulta actual ( es decir, el índice original en el que se produce la consulta actual).
ans[query[j].original index] = current value of fibonacciSum
Al final, imprima la array ans, que almacena el resultado de todas las consultas en el orden en que estaban presentes originalmente.
CPP
// C++ program to find fibonacci sum of
// subarray where all elements <= k
#include <bits/stdc++.h>
using namespace std;
// structure where K is the query parameter
// and original index is the index where the
// query was originally present at.
struct offlineQuery {
int K, originalIndex;
};
// function tp compare queries
bool cmp(offlineQuery q1, offlineQuery q2)
{
return q1.K < q2.K;
}
/* Helper function that multiplies 2 matrices
F and M of size 2*2, and puts the multiplication
result back to F[][] */
void multiply(int F[2][2], int M[2][2])
{
int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
/* Helper function that calculates F[][] raise
to the power n and puts the result in F[][] */
void power(int F[2][2], int n)
{
int i;
int M[2][2] = { { 1, 1 }, { 1, 0 } };
// n - 1 times multiply the
// matrix to {{1, 0}, {0, 1}}
for (i = 2; i <= n; i++)
multiply(F, M);
}
// Returns the nth fibonacci number
int fib(int n)
{
int F[2][2] = { { 1, 1 }, { 1, 0 } };
if (n == 0)
return 0;
power(F, n - 1);
return F[0][0];
}
// Return the answer for each query
int* processQuery(int arr[], int queries[],
int n, int q)
{
// build offline queries where each query
// is of type offlineQuery which stores
// both K and original Index of the query
// in the queries array
offlineQuery* offlineQueries =
new offlineQuery[q];
// Allocate memory to store ans of each query
int* ans = new int[q];
for (int i = 0; i < q; i++) {
int original_index = i;
int K = queries[i];
offlineQueries[i].K = K;
offlineQueries[i].originalIndex =
original_index;
}
// sort offlineQueries[]
sort(offlineQueries, offlineQueries + q, cmp);
// i is pointing to the current position
// array arr fibonacciSum store the
// fibonacciSum till ith index
int i = 0, fibonacciSum = 0;
for (int j = 0; j < q; j++)
{
int currK = offlineQueries[j].K;
int currQueryIndex =
offlineQueries[j].originalIndex;
// keep inserting elements to subset
// while elements are less than
// current query's K value
while (i < n && arr[i] <= currK)
{
fibonacciSum += fib(arr[i]);
i++;
}
// store the current value of
// fibonacci sum in the array ans
// which stores results for the
// queries in the original order
ans[currQueryIndex] = fibonacciSum;
}
return ans;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 2, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
// sort the array arr
sort(arr, arr + n);
// query array stores q queries
int queries[] = { 2, 10, 6 };
int q = sizeof(queries) / sizeof(queries[0]);
// res stores the result of each query
int* res = processQuery(arr, queries, n, q);
for (int i = 0; i < q; i++) {
int ans = res[i];
cout << "Query " << i + 1 << " : "
<< ans << endl;
}
return 0;
}
Python3
# Python3 program to find fibonacci sum of
# subarray where all elements <= k
from bisect import bisect
# Helper function that multiplies 2 matrices
# F and M of size 2*2, and puts the multiplication
# result back to F
def multiply(F, M):
x = F[0][0] * M[0][0] + F[0][1] * M[1][0]
y = F[0][0] * M[0][1] + F[0][1] * M[1][1]
z = F[1][0] * M[0][0] + F[1][1] * M[1][0]
w = F[1][0] * M[0][1] + F[1][1] * M[1][1]
F[0][0] = x
F[0][1] = y
F[1][0] = z
F[1][1] = w
# Helper function that calculates F
# raise to the power n and puts the
# result in F
def power(F, n):
M = [[1, 1], [1, 0]]
# n - 1 times multiply the
# matrix to [[1, 0], [0, 1]]
for i in range(1, n):
multiply(F, M)
# Returns the nth fibonacci number
def fib(n):
F = [[1, 1], [1, 0]]
if (n == 0):
return 0
power(F, n - 1)
return F[0][0]
# Return the answer for each query
def processQuery(arr, queries, n, q):
# build offline queries where each query
# is of type tuple which stores
# both K and original Index of the query
# in the queries array
offlineQueries = [None]*q
# Allocate memory to store ans of each query
ans = [0]*q
for i in range(q) :
original_index = i
K = queries[i]
offlineQueries[i]= (K,original_index)
# sort offlineQueries
offlineQueries.sort()
# i is pointing to the current position
# array arr fibonacciSum store the
# fibonacciSum till ith index
i,fibonacciSum = 0,0
for j in range(q):
currK = offlineQueries[j][0]
currQueryIndex =offlineQueries[j][1]
# keep inserting elements to subset
# while elements are less than
# current query's K value
while (i < n and arr[i] <= currK):
fibonacciSum += fib(arr[i])
i+=1
# store the current value of
# fibonacci sum in the array ans
# which stores results for the
# queries in the original order
ans[currQueryIndex] = fibonacciSum
return ans
# Driver Code
if __name__ == '__main__':
arr = [ 1, 2, 3, 4, 2, 7 ]
n = len(arr)
# sort the array arr
arr.sort()
# query array stores q queries
queries = [ 2, 10, 6 ]
q = len(queries)
# res stores the result of each query
res = processQuery(arr, queries, n, q)
for i in range(q):
ans = res[i]
print("Query {} : {}".format(i+1, ans))
Javascript
// JavaScript program to find fibonacci sum of
// subarray where all elements <= k
// structure where K is the query parameter
// and original index is the index where the
// query was originally present at.
class offlineQuery{
constructor(K, originalIndex){
this.K = K;
this.originalIndex = originalIndex;
}
}
// function tp compare queries
function cmp(q1, q2)
{
return q1.K - q2.K;
}
/* Helper function that multiplies 2 matrices
F and M of size 2*2, and puts the multiplication
result back to F[][] */
function multiply(F, M)
{
x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
/* Helper function that calculates F[][] raise
to the power n and puts the result in F[][] */
function power(F, n)
{
let i;
let M = [[1, 1 ], [1, 0]];
// n - 1 times multiply the
// matrix to {{1, 0}, {0, 1}}
for (i = 2; i <= n; i++)
multiply(F, M);
}
// Returns the nth fibonacci number
function fib(n)
{
let F = [[1, 1],[1, 0]];
if (n == 0)
return 0;
power(F, n - 1);
return F[0][0];
}
// Return the answer for each query
function processQuery(arr, queries, n, q)
{
// build offline queries where each query
// is of type offlineQuery which stores
// both K and original Index of the query
// in the queries array
let offlineQueries = new Array();
// Allocate memory to store ans of each query
let ans = new Array(q).fill(0);
for (let i = 0; i < q; i++) {
let original_index = i;
let K = queries[i];
offlineQueries.push(new offlineQuery(K, original_index));
}
// sort offlineQueries[]
offlineQueries.sort(cmp);
// i is pointing to the current position
// array arr fibonacciSum store the
// fibonacciSum till ith index
let i = 0;
let fibonacciSum = 0;
for (let j = 0; j < q; j++)
{
let currK = offlineQueries[j].K;
let currQueryIndex = offlineQueries[j].originalIndex;
// keep inserting elements to subset
// while elements are less than
// current query's K value
while (i < n && arr[i] <= currK)
{
fibonacciSum += fib(arr[i]);
i++;
}
// store the current value of
// fibonacci sum in the array ans
// which stores results for the
// queries in the original order
ans[currQueryIndex] = fibonacciSum;
}
return ans;
}
// Driver Code
let arr = [1, 2, 3, 4, 2, 7 ];
let n = arr.length;
// sort the array arr
arr.sort(function(a, b){return a - b});
// query array stores q queries
let queries = [2, 10, 6];
let q = queries.length;
// res stores the result of each query
let res = processQuery(arr, queries, n, q);
for (let i = 0; i < q; i++) {
let ans = res[i];
console.log("Query", i+1, ":", ans);
}
// The code is contributed by Gautam goel (gautamgoel962)
Producción:
Query 1 : 3 Query 2 : 21 Query 3 : 8
Complejidad temporal: O(nlogn + qlogq)
Espacio auxiliar: O(q)