Запросы максимальной и минимальной разницы между числами Фибоначчи в заданных диапазонах
Учитывая массив 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.
Подход: идея состоит в том, чтобы использовать концепцию хеширования и префиксного массива сумм для предварительного вычисления и хранения чисел Фибоначчи в двух массивах prefix [] и suffix [] .
После выполнения вышеуказанного предварительного вычисления мы можем проверить, является ли число Фибоначчи или нет в постоянное время. Поэтому для выполнения вышеуказанных операций используется следующий подход:
- Найдите максимальную разницу: чтобы найти максимальную разницу, используется массив префиксов, в котором хранится наибольшее число Фибоначчи меньше 'i' для каждого индекса, и массив суффиксов, в котором хранится наименьшее число Фибоначчи больше 'i' для каждого индекса. . Для каждого запроса {L, R} возвращается префикс [R] - суффикс [L].
- Найдите минимальную разницу: разница между первыми двумя числами в диапазоне {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): РЕКОМЕНДУЕМЫЕ СТАТЬИ |