Minimize cost of converting all array elements to Fibonacci Numbers | Python program for the above approach ; Function to find the N - th Fibonacci Number ; Find the value of a , b , and r ; Find the N - th Fibonacci ; Return the result ; Function to find the Fibonacci number which is nearest to X ; Calculate the value of n for X ; Return the nearest Fibonacci Number ; Function to find the minimum cost to convert all array elements to Fibonacci Numbers ; Stores the total minimum cost ; Traverse the given array arr [ ] ; Find the nearest Fibonacci Number ; Add the cost ; Return the final cost ; Driver Code
import math NEW_LINE def nthFibo ( n ) : NEW_LINE INDENT a = ( 5 ** ( 1 / 2 ) + 1 ) / 2 NEW_LINE b = ( - 5 ** ( 1 / 2 ) + 1 ) / 2 NEW_LINE r = 5 ** ( 1 / 2 ) NEW_LINE ans = ( a ** n - b ** n ) / r NEW_LINE return int ( ans ) NEW_LINE DEDENT def nearFibo ( X ) : NEW_LINE INDENT a = ( 5 ** ( 1 / 2 ) + 1 ) / 2 NEW_LINE n = int ( math . log ( ( 5 ** ( 1 / 2 ) ) * X ) / math . log ( a ) ) NEW_LINE nth = nthFibo ( n ) NEW_LINE nplus = nthFibo ( n + 1 ) NEW_LINE if abs ( X - nth ) < abs ( X - nplus ) : NEW_LINE INDENT return nth NEW_LINE DEDENT else : NEW_LINE INDENT return nplus NEW_LINE DEDENT DEDENT def getCost ( arr ) : NEW_LINE INDENT cost = 0 NEW_LINE for i in arr : NEW_LINE INDENT fibo = nearFibo ( i ) NEW_LINE cost += abs ( i - fibo ) NEW_LINE DEDENT return cost NEW_LINE DEDENT arr = [ 56 , 34 , 23 , 98 , 7 ] NEW_LINE print ( getCost ( arr ) ) NEW_LINE