综合编程

Count of consecutive Fibonacci pairs in the given Array

微信扫一扫,分享到朋友圈

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

link

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

Recommended Posts:

Swift Logging

上一篇

华为P40系列发布 首搭90Hz高刷屏+徕卡五摄影像系统

下一篇

你也可能喜欢

评论已经被关闭。

插入图片

热门栏目

Count of consecutive Fibonacci pairs in the given Array

长按储存图像,分享给朋友