Dadas las consultas Q que contienen rangos en forma de [L, R] , la tarea es encontrar la suma de todos los números que no son de Fibonacci para cada rango en las consultas dadas.
Ejemplos:
Entrada: arr[][] = {{1, 5}, {6, 10}}
Salida: 4 32
Explicación:
Consulta 1: En el rango [1, 5], solo 4 es un número que no es de Fibonacci.
Consulta 2: En el rango [6, 10], 6, 7, 9 y 10 son los números que no son de Fibonacci.
Por lo tanto, 6 + 7 + 9 + 10 = 32.
Entrada: arr[][] = {{10, 20}, {20, 50}}
Salida: 152 10792
Enfoque: la idea es usar una array de suma de prefijos . La suma de todos los números que no son de Fibonacci se calcula previamente y se almacena en una array. Para que cada consulta pueda ser respondida en tiempo O(1). Cada índice de la array almacena la suma de todos los números que no son de Fibonacci desde 1 hasta ese índice. Entonces, para encontrar la suma de todos los números que no son de Fibonacci en un rango, se puede calcular como:
Let the precomputed array is stored in pref[] array sum = pref[R] - pref[L - 1]
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// sum of all non-fibonacci numbers
// in a range from L to R
#include <bits/stdc++.h>
#define ll int
using namespace std;
// Array to precompute the sum of
// non-fibonacci numbers
long long pref[100010];
// Function to find if a number
// is a perfect square
bool isPerfectSquare(int x)
{
int s = sqrt(x);
return (s * s == x);
}
// Function that returns N
// if N is non-fibonacci number
int isNonFibonacci(int n)
{
// N is Fibonacci if one of
// 5*n*n + 4 or 5*n*n - 4 or both
// are perfect square
if (isPerfectSquare(5 * n * n + 4)
|| isPerfectSquare(5 * n * n - 4))
return 0;
else
return n;
}
// Function to precompute sum of
// non-fibonacci Numbers
void compute()
{
for (int i = 1; i <= 100000; ++i) {
pref[i] = pref[i - 1]
+ isNonFibonacci(i);
}
}
// Function to find the sum of all
// non-fibonacci numbers in a range
void printSum(int L, int R)
{
int sum = pref[R] - pref[L - 1];
cout << sum << " ";
}
// Driver Code
int main()
{
// Pre-computation
compute();
int Q = 2;
int arr[][2] = { { 1, 5 },
{ 6, 10 } };
// Loop to find the sum for
// each query
for (int i = 0; i < Q; i++) {
printSum(arr[i][0], arr[i][1]);
}
return 0;
}
Java
// Java implementation to find the
// sum of all non-fibonacci numbers
// in a range from L to R
import java.util.*;
// Array to precompute the sum of
// non-fibonacci numbers
class GFG
{
static long pref[] = new long[100010];
// Function to find if a number
// is a perfect square
static boolean isPerfectSquare(int x)
{
int s =(int)Math.sqrt(x);
return (s * s == x);
}
// Function that returns N
// if N is non-fibonacci number
static int isNonFibonacci(int n)
{
// N is Fibonacci if one of
// 5*n*n + 4 or 5*n*n - 4 or both
// are perfect square
if (isPerfectSquare(5 * n * n + 4)
|| isPerfectSquare(5 * n * n - 4))
return 0;
else
return n;
}
// Function to precompute sum of
// non-fibonacci Numbers
static void compute()
{
for (int i = 1; i <= 100000; ++i) {
pref[i] = pref[i - 1]
+ isNonFibonacci(i);
}
}
// Function to find the sum of all
// non-fibonacci numbers in a range
static void printSum(int L, int R)
{
int sum = (int)(pref[R] - pref[L - 1]);
System.out.print(sum + " ");
}
// Driver Code
public static void main(String []args)
{
// Pre-computation
compute();
int Q = 2;
int arr[][] = { { 1, 5 },
{ 6, 10 } };
// Loop to find the sum for
// each query
for (int i = 0; i < Q; i++) {
printSum(arr[i][0], arr[i][1]);
}
}
}
// This code is contributed by chitranayal
Python3
# Python3 implementation to find the # sum of all non-fibonacci numbers # in a range from L to R from math import sqrt # Array to precompute the sum of # non-fibonacci numbers pref = [0]*100010 # Function to find if a number # is a perfect square def isPerfectSquare(x): s = int(sqrt(x)) if (s * s == x): return True return False # Function that returns N # if N is non-fibonacci number def isNonFibonacci(n): # N is Fibonacci if one of # 5*n*n + 4 or 5*n*n - 4 or both # are perfect square x = 5 * n * n if (isPerfectSquare(x + 4) or isPerfectSquare(x - 4)): return 0 else: return n # Function to precompute sum of # non-fibonacci Numbers def compute(): for i in range(1,100001): pref[i] = pref[i - 1] + isNonFibonacci(i) # Function to find the sum of all # non-fibonacci numbers in a range def printSum(L, R): sum = pref[R] - pref[L-1] print(sum, end=" ") # Driver Code # Pre-computation compute() Q = 2 arr = [[1, 5],[6, 10]] # Loop to find the sum for # each query for i in range(Q): printSum(arr[i][0], arr[i][1]) # This code is contributed by shubhamsingh10
C#
// C# implementation to find the
// sum of all non-fibonacci numbers
// in a range from L to R
using System;
// Array to precompute the sum of
// non-fibonacci numbers
class GFG
{
static long []pref = new long[100010];
// Function to find if a number
// is a perfect square
static bool isPerfectSquare(int x)
{
int s =(int)Math.Sqrt(x);
return (s * s == x);
}
// Function that returns N
// if N is non-fibonacci number
static int isNonFibonacci(int n)
{
// N is Fibonacci if one of
// 5*n*n + 4 or 5*n*n - 4 or both
// are perfect square
if (isPerfectSquare(5 * n * n + 4)
|| isPerfectSquare(5 * n * n - 4))
return 0;
else
return n;
}
// Function to precompute sum of
// non-fibonacci Numbers
static void compute()
{
for (int i = 1; i <= 100000; ++i) {
pref[i] = pref[i - 1]
+ isNonFibonacci(i);
}
}
// Function to find the sum of all
// non-fibonacci numbers in a range
static void printSum(int L, int R)
{
int sum = (int)(pref[R] - pref[L - 1]);
Console.Write(sum + " ");
}
// Driver Code
public static void Main(String []args)
{
// Pre-computation
compute();
int Q = 2;
int [,]arr = { { 1, 5 },
{ 6, 10 } };
// Loop to find the sum for
// each query
for (int i = 0; i < Q; i++) {
printSum(arr[i,0], arr[i,1]);
}
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation to find the
// sum of all non-fibonacci numbers
// in a range from L to R
// Array to precompute the sum of
// non-fibonacci numbers
var pref = Array(100010).fill(0);
// Function to find if a number
// is a perfect square
function isPerfectSquare(x)
{
var s = parseInt(Math.sqrt(x));
return (s * s == x);
}
// Function that returns N
// if N is non-fibonacci number
function isNonFibonacci(n)
{
// N is Fibonacci if one of
// 5*n*n + 4 or 5*n*n - 4 or both
// are perfect square
if (isPerfectSquare(5 * n * n + 4)
|| isPerfectSquare(5 * n * n - 4))
return 0;
else
return n;
}
// Function to precompute sum of
// non-fibonacci Numbers
function compute()
{
for (var i = 1; i <= 100000; ++i) {
pref[i] = pref[i - 1]
+ isNonFibonacci(i);
}
}
// Function to find the sum of all
// non-fibonacci numbers in a range
function printSum(L, R)
{
var sum = pref[R] - pref[L - 1];
document.write(sum + " ");
}
// Driver Code
// Pre-computation
compute();
var Q = 2;
var arr = [ [ 1, 5 ],
[ 6, 10 ] ];
// Loop to find the sum for
// each query
for (var i = 0; i < Q; i++) {
printSum(arr[i][0], arr[i][1]);
}
// This code is contributed by rutvik_56.
</script>
Producción:
4 32
Análisis de rendimiento:
- Complejidad del tiempo: como en el enfoque anterior, hay un cálculo previo que requiere un tiempo O (N) y para responder a cada consulta se necesita un tiempo O (1) .
- Complejidad del espacio auxiliar: como en el enfoque anterior, se usa espacio adicional para precalcular la suma de todos los números que no son de Fibonacci. Por lo tanto, la complejidad del espacio auxiliar será O(N) .