# Count of consecutive Fibonacci pairs in the given Array

Given an array arr[]
, the task is to count the number of consecutive Fibonacci pairs in this array.

#### Examples:

Input:arr[] = { 3, 5, 6, 11 }

Output:1

The only pair is (3, 5) which is consecutive fibonacci pair in the array

Input:arr[] = { 3, 5, 8, 11 }

Output:2

There are two pairs (3, 5) and (5, 8) in the array, which is consecutive Fibonacci pair.

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach:

• Find out all the pairs of the array
.
• For each pair,

• Find the minimum and maximum of the pair
• Find the next consective fibonacci number
after minimum_element
and check that it is equal to the maximum
of the pair.
• If the next consecutive fibonacci number is equal to the maximum element of the pair, then increment the count by 1.
• Return the total count as the required number of pairs.

Below is the implementation of the above approach:

## C++

filter_none

edit

close

play_arrow

brightness_4

code

`// C++ implmentation to count the`
`// consecutive fibonacci pairs in the array`
` `
`#include <bits/stdc++.h>`
`using`
`namespace`
`std;`
` `
`// Function to find the previous`
`// fibonacci for the number N`
`int`
`previousFibonacci(`
`int`
`n)`
`{`
`  `
`double`
`a = n / ((1 +`
`sqrt`
`(5)) / 2.0);`
`  `
`return`
`round(a);`
`}`
` `
`// Function to find the next`
`// fibonacci number for the number N`
`int`
`nextFibonacci(`
`int`
`n)`
`{`
`  `
`double`
`a = n * (1 +`
`sqrt`
`(5)) / 2.0;`
`  `
`return`
`round(a);`
`}`
` `
`// Function to check that a Number`
`// is a perfect square or not`
`bool`
`isPerfectSquare(`
`int`
`x)`
`{`
`  `
`int`
`s =`
`sqrt`
`(x);`
`  `
`return`
`(s * s == x);`
`}`
` `
`// Function to check that a number`
`// is fibonacci number or not`
`bool`
`isFibonacci(`
`int`
`n)`
`{`
`  `
`// N is Fibinacci if one of`
`  `
`// (5*n*n + 4) or (5*n*n - 4)`
`  `
`// is a perferct square`
`  `
`return`
`(isPerfectSquare(5 * n * n + 4)`
`  `
`|| isPerfectSquare(5 * n * n - 4));`
`}`
` `
`// Function to count the fibonacci`
`// pairs in the array`
`int`
`countFibonacciPairs(`
`int`
`arr[],`
`int`
`n)`
`{`
`  `
`int`
`res = 0;`
` `
`  `
`// Loop to iterate over the array`
`  `
`// to choose all pairs of the array`
`  `
`for`
`(`
`int`
`i = 0; i < n; i++)`
`  `
`for`
`(`
`int`
`j = i + 1; j < n; j++)`
` `
`  `
`// Condition to check if both`
`  `
`// the number of pair is a`
`  `
`// fibonacci number`
`  `
`if`
`(isFibonacci(arr[i])`
`  `
`&& isFibonacci(arr[j])) {`
` `
`  `
`int`
`prevFib = previousFibonacci(arr[i]);`
`  `
`int`
`nextFib = nextFibonacci(arr[i]);`
` `
`  `
`// Condition to check if both`
`  `
`// the number form consecutive`
`  `
`// fibonacci numbers`
`  `
`if`
`(prevFib == arr[j]`
`  `
`|| nextFib == arr[j]) {`
`  `
`res++;`
`  `
`}`
`  `
`}`
` `
`  `
`return`
`res;`
`}`
` `
`// Driver Code`
`int`
`main()`
`{`
`  `
`int`
`a[] = { 3, 5, 8, 11 };`
`  `
`int`
`n =`
`sizeof`
`(a) /`
`sizeof`
`(a[0]);`
`  `
`cout << countFibonacciPairs(a, n);`
`  `
`return`
`0;`
`}`

chevron_right

filter_none

Output:

#### Performance Analysis:

• Time Complexity:
As in the above approach, there are two nested loops which takes O(N 2
) time, Hence the Time Complexity will be
O(N 2
)

.
• Space Complexity:
As in the above approach, there is no extra space used, Hence the space complexity will be O(1)
.

My Personal Notes

arrow_drop_up