Given Q queries containing ranges in the form of [L, R], the task is to find the sum of all non-fibonacci numbers for each range in the given queries.
Examples:
Input: arr[][] = {{1, 5}, {6, 10}}
Output: 4 32
Explanation:
Query 1: In the range [1, 5], only 4 is a non-fibonacci number.
Query 2: In the range [6, 10], 6, 7, 9 and 10 are the non-fibonacci numbers.
Therefore, 6 + 7 + 9 + 10 = 32.
Input: arr[][] = {{10, 20}, {20, 50}}
Output: 152 10792
Approach: The idea is to use a prefix sum array. The sum of all non-fibonacci numbers is precomputed and stored in an array. So that every query can be answered in O(1) time. Every index of the array stores the sum of all non-fibonacci numbers from 1 to that index. So for finding the sum of all non-fibonacci numbers in a range can be computed as:
Let the precomputed array is stored in pref[] array sum = pref[R] - pref[L - 1]
Below is the implementation of the above approach:
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 = 2arr = [[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> |
Output:
4 32
Performance Analysis:
- Time Complexity: As in the above approach, There is pre-computation which takes O(N) time and to answer each query it takes O(1) time.
- Auxiliary Space Complexity: As in the above approach, There is extra space used to precompute the sum of all non-fibonacci number. Hence the auxiliary space complexity will be O(N).
