Dada una array arr[][] que contiene N consultas de la forma [L, R] , la tarea es encontrar la diferencia máxima entre dos números de Fibonacci en el rango de cada consulta. Si no hay números de Fibonacci en el rango o solo un número de Fibonacci, imprima 0.
Nota: Todos los rangos están por debajo de 100005.
Ejemplos:
Entrada: N = 2, arr[][] = {{2, 2}, {2, 5}}
Salida: 0 3
Explicación:
En la primera consulta, solo hay un número de Fibonacci. Entonces, la respuesta es 0.
En la segunda consulta, 2 es el mínimo y 5 es el número máximo de Fibonacci.
Por lo tanto, la diferencia máxima = 3.Entrada: N = 2, arr[][] = {{2, 21}, {30, 150}}
Salida: 19 110
Explicación:
En la primera consulta, 2 es el número de Fibonacci mínimo y 5 es el máximo.
Por lo tanto, la diferencia máxima = 19.
En la segunda consulta, 34 es el mínimo y 144 es el número de Fibonacci máximo.
Por lo tanto, la diferencia máxima = 110.
Enfoque: la idea es usar el concepto de hashing y la array de suma de prefijos para precalcular y almacenar los números de Fibonacci en dos arrays prefijo[] y sufijo[] .
Después de realizar el cálculo previo anterior, podemos comprobar si un número es un Fibonacci o no en tiempo constante. Por lo tanto, para realizar las operaciones anteriores, se utiliza el siguiente enfoque:
- Encuentre la diferencia máxima: para encontrar la diferencia máxima, se usa la array de prefijos que almacena el número de Fibonacci más grande menor que ‘i’ para cada índice y una array de sufijos que almacena el número de Fibonacci más pequeño mayor que ‘i’ para cada índice . Para cada consulta {L, R}, se devuelve prefijo[R] – sufijo[L] .
- Encuentra la diferencia mínima: La diferencia entre los dos primeros números en el rango {L, R} es la diferencia mínima posible.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the maximum differences
// between two Fibonacci numbers in given ranges
#include <bits/stdc++.h>
using namespace std;
#define MAX 100005
bool isFib[MAX];
int prefix[MAX], suffix[MAX];
// Function to precompute the Fibonacci,
// Prefix array and Suffix array
void precompute()
{
// Initializing it with False
memset(isFib, false, sizeof(isFib));
// Variable to store the Fibonacci
// numbers
// Marking the first two Fibonacci numbers
// as True in the array
int prev = 0, curr = 1;
isFib[prev] = isFib[curr] = true;
// Loop to iterate until the maximum number
while (curr < MAX) {
int temp = curr + prev;
isFib[temp] = true;
prev = curr;
curr = temp;
}
prefix[1] = 1;
suffix[MAX - 1] = 1e9 + 7;
// Precomputing Prefix array
for (int i = 2; i < MAX; i++) {
// If the number is a Fibonacci number,
// then adding it to the prefix array
if (isFib[i])
prefix[i] = i;
else
prefix[i] = prefix[i - 1];
}
// Precompute Suffix array
for (int i = MAX - 1; i > 1; i--) {
if (isFib[i])
suffix[i] = i;
else
suffix[i] = suffix[i + 1];
}
}
// Function to solve each query
int query(int L, int R)
{
if (prefix[R] < L || suffix[L] > R)
return 0;
else
return prefix[R] - suffix[L];
}
// Function to return the minimum difference
// between any two fibonacci numbers
// from the given range [L, R]
int minDifference(int L, int R)
{
// Find the first Fibonacci numbers
// from the range
int fst = 0;
for (int i = L; i <= R; i++) {
if (isFib[i]) {
fst = i;
break;
}
}
// Find the second Fibonacci numbers
// from the range
int snd = 0;
for (int i = fst + 1; i <= R; i++) {
if (isFib[i]) {
snd = i;
break;
}
}
// If the number of fibonacci numbers in
// the given range is < 2
if (snd == 0)
return -1;
// To store the minimum difference between
// two consecutive fibonacci numbers from the range
int diff = snd - fst;
// Range left to check for fibonacci numbers
int left = snd + 1;
int right = R;
// For every integer in the range
for (int i = left; i <= right; i++) {
// If the current integer is fibonacci
if (isFib[i]) {
// If the difference between i
// and snd is minimum so far
if (i - snd <= diff) {
fst = snd;
snd = i;
diff = snd - fst;
}
}
}
return diff;
}
// Function to print the answer
// for every query
void findAns(int arr[][2], int q)
{
precompute();
// Finding the answer for every query
for (int i = 0; i < q; i++) {
cout << "Maximum Difference: "
<< query(arr[i][0], arr[i][1])
<< endl;
cout << "Minimum Difference: "
<< minDifference(arr[i][0], arr[i][1])
<< endl;
}
}
// Driver code
int main()
{
int q = 1;
int arr[][2] = { { 21, 100 } };
findAns(arr, q);
return 0;
}
Java
// Java program to find the maximum
// differences between two Fibonacci
// numbers in given ranges
import java.util.*;
import java.lang.*;
class GFG{
static final int MAX = 100005;
static boolean isFib[] = new boolean[MAX];
static int[] prefix = new int[MAX],
suffix = new int[MAX];
// Function to precompute the Fibonacci,
// Prefix array and Suffix array
static void precompute()
{
// Variable to store the Fibonacci
// numbers
// Marking the first two Fibonacci
// numbers as True in the array
int prev = 0, curr = 1;
isFib[prev] = isFib[curr] = true;
// Loop to iterate until the
// maximum number
while (curr + prev < MAX)
{
int temp = curr + prev;
isFib[temp] = true;
prev = curr;
curr = temp;
}
prefix[1] = 1;
suffix[MAX - 1] = (int)1e9 + 7;
// Precomputing Prefix array
for(int i = 2; i < MAX; i++)
{
// If the number is a Fibonacci
// number, then adding it to the
// prefix array
if (isFib[i])
prefix[i] = i;
else
prefix[i] = prefix[i - 1];
}
// Precompute Suffix array
for(int i = MAX - 2; i > 1; i--)
{
if (isFib[i])
suffix[i] = i;
else
suffix[i] = suffix[i + 1];
}
}
// Function to solve each query
static int query(int L, int R)
{
if (prefix[R] < L || suffix[L] > R)
return 0;
else
return prefix[R] - suffix[L];
}
// Function to return the minimum
// difference between any two
// fibonacci numbers from the
// given range [L, R]
static int minDifference(int L, int R)
{
// Find the first Fibonacci numbers
// from the range
int fst = 0;
for(int i = L; i <= R; i++)
{
if (isFib[i])
{
fst = i;
break;
}
}
// Find the second Fibonacci numbers
// from the range
int snd = 0;
for(int i = fst + 1; i <= R; i++)
{
if (isFib[i])
{
snd = i;
break;
}
}
// If the number of fibonacci
// numbers in the given range is < 2
if (snd == 0)
return -1;
// To store the minimum difference
// between two consecutive fibonacci
// numbers from the range
int diff = snd - fst;
// Range left to check for
// fibonacci numbers
int left = snd + 1;
int right = R;
// For every integer in the range
for(int i = left; i <= right; i++)
{
// If the current integer is fibonacci
if (isFib[i])
{
// If the difference between i
// and snd is minimum so far
if (i - snd <= diff)
{
fst = snd;
snd = i;
diff = snd - fst;
}
}
}
return diff;
}
// Function to print the answer
// for every query
static void findAns(int arr[][], int q)
{
precompute();
// Finding the answer for every query
for(int i = 0; i < q; i++)
{
System.out.println("Maximum Difference: " +
query(arr[i][0], arr[i][1]));
System.out.println("Minimum Difference: " +
minDifference(arr[i][0], arr[i][1]));
}
}
// Driver code
public static void main(String[] args)
{
int q = 1;
int arr[][] = { { 21, 100 } };
findAns(arr, q);
}
}
// This code is contributed by offbeat
Python3
# Python3 program to find the maximum differences
# between two Fibonacci numbers in given ranges
MAX = 100005
isFib = [False]*MAX
prefix = [0]*MAX
suffix = [0]*MAX
# Function to precompute the Fibonacci,
# Prefix array and Suffix array
def precompute():
# Marking the first two Fibonacci numbers
# as True in the array
prev , curr = 0 , 1
isFib[prev] = True
isFib[curr] = True
# Loop to iterate until the maximum number
while (curr < MAX):
temp = curr + prev
if temp<MAX:
isFib[temp] = True
prev = curr
curr = temp
prefix[1] = 1
suffix[MAX - 1] = 1000000007
# Precomputing Prefix array
for i in range(2, MAX):
# If the number is a Fibonacci number,
# then adding it to the prefix array
if (isFib[i]):
prefix[i] = i
else:
prefix[i] = prefix[i - 1]
# Precompute Suffix array
for i in range(MAX - 2, 1, -1):
if (isFib[i]):
suffix[i] = i
else:
suffix[i] = suffix[i + 1]
# Function to solve each query
def query(L, R):
if (prefix[R] < L or suffix[L] > R):
return 0
else:
return prefix[R] - suffix[L]
# Function to return the minimum difference
# between any two fibonacci numbers
# from the given range [L, R]
def minDifference(L, R):
# Find the first Fibonacci numbers
# from the range
fst = 0
for i in range(L, R + 1):
if (isFib[i]):
fst = i
break
# Find the second Fibonacci numbers
# from the range
snd = 0
for i in range(fst + 1, R + 1 ):
if (isFib[i]):
snd = i
break
# If the number of fibonacci numbers in
# the given range is < 2
if (snd == 0):
return -1
# To store the minimum difference between
# two consecutive fibonacci numbers from the range
diff = snd - fst
# Range left to check for fibonacci numbers
left = snd + 1
right = R
# For every integer in the range
for i in range(left, right + 1):
# If the current integer is fibonacci
if (isFib[i]):
# If the difference between i
# and snd is minimum so far
if (i - snd <= diff):
fst = snd
snd = i
diff = snd - fst
return diff
# Function to print the answer
# for every query
def findAns(arr, q):
precompute()
# Finding the answer for every query
for i in range(q):
print( "Maximum Difference: "
, query(arr[i][0], arr[i][1]))
print("Minimum Difference: "
, minDifference(arr[i][0], arr[i][1]))
# Driver code
if __name__ == "__main__":
q = 1
arr = [ [ 21, 100 ] ]
findAns(arr, q)
# This code is contributed by chitranayal
C#
using System;
// C# program to find the maximum
// differences between two Fibonacci
// numbers in given ranges
public class GFG{
static int MAX = 100005;
static bool[] isFib = new bool[MAX];
static int[] prefix = new int[MAX],
suffix = new int[MAX];
// Function to precompute the Fibonacci,
// Prefix array and Suffix array
static void precompute()
{
// Variable to store the Fibonacci
// numbers
// Marking the first two Fibonacci
// numbers as True in the array
int prev = 0, curr = 1;
isFib[prev] = isFib[curr] = true;
// Loop to iterate until the
// maximum number
while (curr + prev < MAX)
{
int temp = curr + prev;
isFib[temp] = true;
prev = curr;
curr = temp;
}
prefix[1] = 1;
suffix[MAX - 1] = (int)1e9 + 7;
// Precomputing Prefix array
for(int i = 2; i < MAX; i++)
{
// If the number is a Fibonacci
// number, then adding it to the
// prefix array
if (isFib[i])
prefix[i] = i;
else
prefix[i] = prefix[i - 1];
}
// Precompute Suffix array
for(int i = MAX - 2; i > 1; i--)
{
if (isFib[i])
suffix[i] = i;
else
suffix[i] = suffix[i + 1];
}
}
// Function to solve each query
static int query(int L, int R)
{
if (prefix[R] < L || suffix[L] > R)
return 0;
else
return prefix[R] - suffix[L];
}
// Function to return the minimum
// difference between any two
// fibonacci numbers from the
// given range [L, R]
static int minDifference(int L, int R)
{
// Find the first Fibonacci numbers
// from the range
int fst = 0;
for(int i = L; i <= R; i++)
{
if (isFib[i])
{
fst = i;
break;
}
}
// Find the second Fibonacci numbers
// from the range
int snd = 0;
for(int i = fst + 1; i <= R; i++)
{
if (isFib[i])
{
snd = i;
break;
}
}
// If the number of fibonacci
// numbers in the given range is < 2
if (snd == 0)
return -1;
// To store the minimum difference
// between two consecutive fibonacci
// numbers from the range
int diff = snd - fst;
// Range left to check for
// fibonacci numbers
int left = snd + 1;
int right = R;
// For every integer in the range
for(int i = left; i <= right; i++)
{
// If the current integer is fibonacci
if (isFib[i])
{
// If the difference between i
// and snd is minimum so far
if (i - snd <= diff)
{
fst = snd;
snd = i;
diff = snd - fst;
}
}
}
return diff;
}
// Function to print the answer
// for every query
static void findAns(int[,] arr, int q)
{
precompute();
// Finding the answer for every query
for(int i = 0; i < q; i++)
{
Console.WriteLine("Maximum Difference: " +
query(arr[i,0], arr[i,1]));
Console.WriteLine("Minimum Difference: " +
minDifference(arr[i,0], arr[i,1]));
}
}
// Driver code
static public void Main ()
{
int q = 1;
int[,] arr = { { 21, 100 } };
findAns(arr, q);
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// JavaScript program to find the maximum differences
// between two Fibonacci numbers in given ranges
let MAX = 100005
let isFib = new Array(MAX);
let prefix = new Array(MAX)
let suffix = new Array(MAX);
// Function to precompute the Fibonacci,
// Prefix array and Suffix array
function precompute()
{
// Initializing it with False
isFib.fill(false);
// Variable to store the Fibonacci
// numbers
// Marking the first two Fibonacci numbers
// as True in the array
let prev = 0, curr = 1;
isFib[prev] = isFib[curr] = true;
// Loop to iterate until the maximum number
while (curr < MAX) {
let temp = curr + prev;
isFib[temp] = true;
prev = curr;
curr = temp;
}
prefix[1] = 1;
suffix[MAX - 1] = 1e9 + 7;
// Precomputing Prefix array
for (let i = 2; i < MAX; i++) {
// If the number is a Fibonacci number,
// then adding it to the prefix array
if (isFib[i])
prefix[i] = i;
else
prefix[i] = prefix[i - 1];
}
// Precompute Suffix array
for (let i = MAX - 1; i > 1; i--) {
if (isFib[i])
suffix[i] = i;
else
suffix[i] = suffix[i + 1];
}
}
// Function to solve each query
function query(L, R)
{
if (prefix[R] < L || suffix[L] > R)
return 0;
else
return prefix[R] - suffix[L];
}
// Function to return the minimum difference
// between any two fibonacci numbers
// from the given range [L, R]
function minDifference(L, R)
{
// Find the first Fibonacci numbers
// from the range
let fst = 0;
for (let i = L; i <= R; i++) {
if (isFib[i]) {
fst = i;
break;
}
}
// Find the second Fibonacci numbers
// from the range
let snd = 0;
for (let i = fst + 1; i <= R; i++) {
if (isFib[i]) {
snd = i;
break;
}
}
// If the number of fibonacci numbers in
// the given range is < 2
if (snd == 0)
return -1;
// To store the minimum difference between
// two consecutive fibonacci numbers from the range
let diff = snd - fst;
// Range left to check for fibonacci numbers
let left = snd + 1;
let right = R;
// For every integer in the range
for (let i = left; i <= right; i++) {
// If the current integer is fibonacci
if (isFib[i]) {
// If the difference between i
// and snd is minimum so far
if (i - snd <= diff) {
fst = snd;
snd = i;
diff = snd - fst;
}
}
}
return diff;
}
// Function to print the answer
// for every query
function findAns(arr, q)
{
precompute();
// Finding the answer for every query
for (let i = 0; i < q; i++) {
document.write("Maximum Difference: "
+ query(arr[i][0], arr[i][1])
+ "<br>");
document.write("Minimum Difference: "
+ minDifference(arr[i][0], arr[i][1])
+ "<br>");
}
}
// Driver code
let q = 1;
let arr = [ [ 21, 100 ] ];
findAns(arr, q);
</script>
Producción:
Maximum Difference: 68 Minimum Difference: 13
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA