Запросы максимальной и минимальной разницы между числами Фибоначчи в заданных диапазонах

Опубликовано: 7 Января, 2022

Учитывая массив arr [] [], содержащий N запросов формы [L, R] , задача состоит в том, чтобы найти максимальную разницу между двумя числами Фибоначчи в диапазоне для каждого запроса. Если в диапазоне нет чисел Фибоначчи или только одно число Фибоначчи, выведите 0.
Примечание: все диапазоны ниже 100005.

Примеры:

Input: N = 2, arr[][] = {{2, 2}, {2, 5}} 
Output: 0 3 
Explanation: 
In the first query, there is only one Fibonacci number. So, the answer is 0. 
In the second query, 2 is the minimum and 5 is the maximum Fibonacci number. 
Therefore, the maximum difference = 3. 

Input: N = 2, arr[][] = {{2, 21}, {30, 150}} 
Output: 19 110 
Explanation: 
In the first query, 2 is the minimum and 5 is the maximum Fibonacci number. 
Therefore, the maximum difference = 19. 
In the second query, 34 is the minimum and 144 is the maximum Fibonacci number. 
Therefore, the maximum difference = 110. 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: идея состоит в том, чтобы использовать концепцию хеширования и префиксного массива сумм для предварительного вычисления и хранения чисел Фибоначчи в двух массивах prefix [] и suffix [] .

После выполнения вышеуказанного предварительного вычисления мы можем проверить, является ли число Фибоначчи или нет в постоянное время. Поэтому для выполнения вышеуказанных операций используется следующий подход:

  1. Найдите максимальную разницу: чтобы найти максимальную разницу, используется массив префиксов, в котором хранится наибольшее число Фибоначчи меньше 'i' для каждого индекса, и массив суффиксов, в котором хранится наименьшее число Фибоначчи больше 'i' для каждого индекса. . Для каждого запроса {L, R} возвращается префикс [R] - суффикс [L].
  2. Найдите минимальную разницу: разница между первыми двумя числами в диапазоне {L, R} - это минимально возможная разница.

Below is the implementation of the above approach:  

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):