Given an array arr[] containing Q positive integers and two numbers A and B, the task is to find the number of ordered pairs (x, y) for every number N, in array arr, such that:
- They satisfy the equation A*x + B*y = N, and
- x and y are Fibonacci numbers.
Examples:
Input: arr[] = {15, 25}, A = 1, B = 2
Output: 2 1
Explanation:
For 15: There are 2 ordered pairs (x, y) = (13, 1) & (5, 5) such that 1*x + 2*y = 15
For 25: There is only one ordered pair (x, y) = (21, 2) such that 1*x + 2*y = 25
Input: arr[] = {50, 150}, A = 5, B = 10
Output: 1 0
Naive Approach: The naive approach for this problem is:
- For every query N in the array, compute the Fibonacci numbers up to N
- Check for all possible pairs, from this Fibonacci numbers, if it satisfies the given condition A*x + B*y = N.
Time complexity: O(N2)
Efficient Approach:
- Precompute all the Fibonacci numbers and store it in an array.
- Now, iterate over the Fibonacci numbers and for all the possible combinations, update the number of ordered pairs for every number in range [1, max(arr)], and store it in another array.
- Now, for every query N, the number of ordered pairs can be answered in constant time.
Below is the implementation of the above approach:
C++
// C++ program to find the count of// Fibonacci pairs (x, y) which// satisfy the equation Ax+By=N#include <bits/stdc++.h>#define size 10001using namespace std;// Array to store the Fibonacci numberslong long fib[100010];// Array to store the number of ordered pairsint freq[100010];// Function to find if a number// is a perfect squarebool isPerfectSquare(int x){ int s = sqrt(x); return (s * s == x);}// Function that returns 1// if N is non-fibonacci number else 0int isFibonacci(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 1; return 0;}// Function to store the fibonacci numbers// and their frequency in form a * x + b * yvoid compute(int a, int b){ // Storing the Fibonacci numbers for (int i = 1; i < 100010; i++) { fib[i] = isFibonacci(i); } // For loop to find all the possible // combinations of the Fibonacci numbers for (int x = 1; x < 100010; x++) { for (int y = 1; y < size; y++) { // Finding the number of ordered pairs if (fib[x] == 1 && fib[y] == 1 && a * x + b * y < 100010) { freq[a * x + b * y]++; } } }}// Driver codeint main(){ int Q = 2, A = 5, B = 10; compute(A, B); int arr[Q] = { 50, 150 }; // Find the ordered pair for every query for (int i = 0; i < Q; i++) { cout << freq[arr[i]] << " "; } return 0;} |
Java
// Java program to find the count of// Fibonacci pairs (x, y) which// satisfy the equation Ax+By=Nclass GFG{ static final int size = 10001;// Array to store the Fibonacci numbersstatic long []fib = new long[100010]; // Array to store the number of ordered pairsstatic int []freq = new int[100010]; // Function to find if a number// is a perfect squarestatic boolean isPerfectSquare(int x){ int s = (int) Math.sqrt(x); return (s * s == x);} // Function that returns 1// if N is non-fibonacci number else 0static int isFibonacci(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 1; return 0;} // Function to store the fibonacci numbers// and their frequency in form a * x + b * ystatic void compute(int a, int b){ // Storing the Fibonacci numbers for (int i = 1; i < 100010; i++) { fib[i] = isFibonacci(i); } // For loop to find all the possible // combinations of the Fibonacci numbers for (int x = 1; x < 100010; x++) { for (int y = 1; y < size; y++) { // Finding the number of ordered pairs if (fib[x] == 1 && fib[y] == 1 && a * x + b * y < 100010) { freq[a * x + b * y]++; } } }} // Driver codepublic static void main(String[] args){ int Q = 2, A = 5, B = 10; compute(A, B); int arr[] = { 50, 150 }; // Find the ordered pair for every query for (int i = 0; i < Q; i++) { System.out.print(freq[arr[i]]+ " "); }}}// This code is contributed by PrinciRaj1992 |
Python 3
# Python program to find the count of# Fibonacci pairs (x, y) which# satisfy the equation Ax+By=Nimport mathsize = 101# Array to store the Fibonacci numbersfib = [0]*100010# Array to store the number of ordered pairsfreq = [0]*(100010)# Function to find if a number# is a perfect squaredef isPerfectSquare(x): s = int(math.sqrt(x)) return (s * s) == x# Function that returns 1# if N is non-fibonacci number else 0def isFibonacci(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) or isPerfectSquare(5 * n * n - 4)): return 1; return 0;# Function to store the fibonacci numbers# and their frequency in form a * x + b * ydef compute( a, b): # Storing the Fibonacci numbers for i in range(1, 100010): fib[i] = isFibonacci(i) # For loop to find all the possible # combinations of the Fibonacci numbers for x in range(1, 100010): for y in range(1, size): # Finding the number of ordered pairs if (fib[x] == 1 and fib[y] == 1 and a * x + b * y < 100010): freq[a * x + b * y] += 1 # Driver codeQ = 2A = 5B = 10compute(A, B);arr = [ 50, 150 ]# Find the ordered pair for every queryfor i in range(Q): print(freq[arr[i]], end=" ") # This code is contributed by ANKITKUMAR34 |
C#
// C# program to find the count of// Fibonacci pairs (x, y) which// satisfy the equation Ax+By=Nusing System;class GFG{ static readonly int size = 10001; // Array to store the Fibonacci numbersstatic long []fib = new long[100010]; // Array to store the number of ordered pairsstatic int []freq = new int[100010]; // Function to find if a number// is a perfect squarestatic bool isPerfectSquare(int x){ int s = (int) Math.Sqrt(x); return (s * s == x);} // Function that returns 1// if N is non-fibonacci number else 0static int isFibonacci(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 1; return 0;} // Function to store the fibonacci numbers// and their frequency in form a * x + b * ystatic void compute(int a, int b){ // Storing the Fibonacci numbers for (int i = 1; i < 100010; i++) { fib[i] = isFibonacci(i); } // For loop to find all the possible // combinations of the Fibonacci numbers for (int x = 1; x < 100010; x++) { for (int y = 1; y < size; y++) { // Finding the number of ordered pairs if (fib[x] == 1 && fib[y] == 1 && a * x + b * y < 100010) { freq[a * x + b * y]++; } } }} // Driver codepublic static void Main(String[] args){ int Q = 2, A = 5, B = 10; compute(A, B); int []arr = { 50, 150 }; // Find the ordered pair for every query for (int i = 0; i < Q; i++) { Console.Write(freq[arr[i]]+ " "); }}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to find the count of// Fibonacci pairs (x, y) which// satisfy the equation Ax+By=Nvar size = 10001// Array to store the Fibonacci numbersvar fib = Array(100010).fill(0);// Array to store the number of ordered pairsvar freq = Array(100010).fill(0);// Function to find if a number// is a perfect squarefunction isPerfectSquare(x){ var s = parseInt(Math.sqrt(x)); return (s * s == x);}// Function that returns 1// if N is non-fibonacci number else 0function isFibonacci(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 1; return 0;}// Function to store the fibonacci numbers// and their frequency in form a * x + b * yfunction compute(a, b){ // Storing the Fibonacci numbers for (var i = 1; i < 100010; i++) { fib[i] = isFibonacci(i); } // For loop to find all the possible // combinations of the Fibonacci numbers for (var x = 1; x < 100010; x++) { for (var y = 1; y < size; y++) { // Finding the number of ordered pairs if (fib[x] == 1 && fib[y] == 1 && a * x + b * y < 100010) { freq[a * x + b * y]++; } } }}// Driver codevar Q = 2, A = 5, B = 10;compute(A, B);var arr = [ 50, 150 ];// Find the ordered pair for every queryfor (var i = 0; i < Q; i++){ document.write(freq[arr[i]] + " ");}// This code is contributed by rutvik_56.</script> |
Output:
1 0
Time Complexity: O(size + 100010)
Auxiliary Space: O(size + 100010)
