Write A Program Nearest Fibonacci Number to N

Given a positive integer number N, the task is to seek out the closest number to the given integer number N. If there are Fibonacci Numbers having same distinction from N, then print the smaller value.

#Examples:
Input: N = 20
Output: 21
Explain: Nearest Fibonacci number to 20 is 21.

Input: N = 17
Output: 13

Approach How To Solve The Problem Step By Step:

If N is equal to 0, then print 0 as the result.
Initialize a variable, say “ans” [is a variable], to store the Fibonacci Number nearest to N.
Initialize two variables, say “First” [is a variable] as 0, and “Second” [is a variable] as 1, to store the first and second terms of the Fibonacci Series.
Store the sum of First and Second in a variable, say “Third” [is a variable].
Iterate until the value of Third is at most N and perform the following steps:
- Update the value of First to Second and Second to Third.
- Store the sum of First and Second in the variable Third.
If the absolute difference of Second and N is at most the value of Third and N, then update the value of ans as Second.
Otherwise, update the value of ans as Third.
After completing the above steps, print the value of ans as the result.

Below is the implementation of above algorithm

// C++ program for the above approach

#include <bits/stdc++.h>
using namespace std;

// Function to find the Fibonacci
// number which is nearest to N
void nearestFibonacci(int num)
{
	// Base Case
	if (num == 0) {
		cout << 0;
		return;
	}

	// Initialize the first & second
	// terms of the Fibonacci series
	int first = 0, second = 1;

	// Store the third term
	int third = first + second;

	// Iterate until the third term
	// is less than or equal to num
	while (third <= num) {

		// Update the first
		first = second;

		// Update the second
		second = third;

		// Update the third
		third = first + second;
	}

	// Store the Fibonacci number
	// having smaller difference with N
	int ans = (abs(third - num)
			>= abs(second - num))
				? second
				: third;

	// Print the result
	cout << ans;
}

// Driver Code
int main()
{
	int N = 17;
	nearestFibonacci(N);

	return 0;
}

Output:

Time Complexity: O(log N)
Auxiliary Space: O(1)

Please write comments or WhatsApp if you find anything incorrect, or you want to share more information about this topic discussed above.