Minimize cost of converting all array elements to Fibonacci Numbers
Given an array arr[] consisting of N integers, the task is to minimize the cost of converting all array elements to a Fibonacci Number, where the cost of converting a number A to B is the absolute difference between A and B.
Examples:
Input: arr[] = {56, 34, 23, 98, 7}
Output: 13
Explanation:
Following are the conversion of elements required to make all array elements as Fibonacci Numbers:
- Convert arr[0](= 56) to 55. Cost = | 56 – 55| = 1.
- Convert arr[1](= 34) to 34. Cost = |34 – 34| = 0.
- Convert arr[2](= 23) to 21. Cost = |23 – 21| = 2.
- Convert arr[3](= 98) to 89. Cost = |98 – 89| = 9.
- Convert arr[4](= 7) to 8. Cost = |7 – 8| = 1.
Therefore, the total cost of changing all array elements to Fibonacci numbers = 1 + 0 + 2 + 9 + 1 = 13.
Input: {543, 32, 7, 23, 641}
Output: 103
Approach: The given problem can be solved by replacing each array element with its nearest Fibonacci Number to get the minimum cost for changing all array elements to Fibonacci Number. Follow the step below to solve the given problem:
- Initialize a variable say, cost that stores the minimum cost of changing all array elements to Fibonacci Number.
- Traverse the given array arr[] and perform the following steps:
- To find the Fibonacci number closest to arr[i], first, find the value of N such that Nth Fibonacci Number is arr[i] using the formula
- Now, find the Nth and (N + 1)th Fibonacci Number, say X and Y respectively and add the minimum of absolute values of (X – arr[i]) and (Y – arr[i]) to the cost.
- After completing the above steps, print the value of cost as the resultant minimum cost.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the // N-th Fibonacci Number int nthFibo( int n) { // Find the value of a, b, and r double a = ( pow (5, 0.5) + 1) / 2; double b = (-1*( pow (5, 0.5) ) + 1) / 2; double r = pow (5, 0.5); // Find the N-th Fibonacci double ans = ( pow (a, n) - pow (b, n)) / r; // Return the result return int (ans); } // Function to find the Fibonacci // number which is nearest to X int nearFibo( int X) { double a = ( pow (5, 0.5) + 1) / 2; // Calculate the value of n for X int n = int ( log (( pow (5, 0.5)) * X) / log (a)); int nth = nthFibo(n); int nplus = nthFibo(n + 1); // Return the nearest // Fibonacci Number if ( abs (X - nth) < abs (X - nplus)) return nth; else return nplus; } // Function to find the minimum // cost to convert all array // elements to Fibonacci Numbers int getCost( int arr[], int n) { // Stores the total minimum cost int cost = 0; // Traverse the given array arr[] for ( int i = 0; i < n; i++) { // Find the nearest // Fibonacci Number int fibo = nearFibo(arr[i]); // Add the cost cost += abs (arr[i] - fibo); } // Return the final cost return cost; } // Driver Code int main() { int arr[] = { 56, 34, 23, 98, 7 }; int n = sizeof (arr) / sizeof (arr[0]); cout << (getCost(arr, n)); } // This code is contributed by ukasp |
Java
// Java program for the above approach import java.util.*; import java.lang.*; class GFG { // Function to find the // N-th Fibonacci Number static int nthFibo( int n) { // Find the value of a, b, and r double a = (Math.pow( 5 , 0.5 ) + 1 ) / 2 ; double b = (- 1 *(Math.pow( 5 , 0.5 ) ) + 1 ) / 2 ; double r = Math.pow( 5 , 0.5 ); // Find the N-th Fibonacci double ans = (Math.pow(a, n) - Math.pow(b, n)) / r; // Return the result return ( int )ans; } // Function to find the Fibonacci // number which is nearest to X static int nearFibo( int X) { double a = (Math.pow( 5 , 0.5 ) + 1 ) / 2 ; // Calculate the value of n for X int n = ( int )(Math.log((Math.pow( 5 , 0.5 )) * X) / Math.log(a)); int nth = nthFibo(n); int nplus = nthFibo(n + 1 ); // Return the nearest // Fibonacci Number if (Math.abs(X - nth) < Math.abs(X - nplus)) return nth; else return nplus; } // Function to find the minimum // cost to convert all array // elements to Fibonacci Numbers static int getCost( int arr[], int n) { // Stores the total minimum cost int cost = 0 ; // Traverse the given array arr[] for ( int i = 0 ; i < n; i++) { // Find the nearest // Fibonacci Number int fibo = nearFibo(arr[i]); // Add the cost cost += Math.abs(arr[i] - fibo); } // Return the final cost return cost; } // Driver code public static void main (String[] args) { int arr[] = { 56 , 34 , 23 , 98 , 7 }; int n = arr.length; System.out.print(getCost(arr, n)); } } // This code is contributed by offbeat |
Python3
# Python program for the above approach import math # Function to find the # N-th Fibonacci Number def nthFibo(n): # Find the value of a, b, and r a = ( 5 * * ( 1 / 2 ) + 1 ) / 2 b = ( - 5 * * ( 1 / 2 ) + 1 ) / 2 r = 5 * * ( 1 / 2 ) # Find the N-th Fibonacci ans = (a * * n - b * * n) / r # Return the result return int (ans) # Function to find the Fibonacci # number which is nearest to X def nearFibo(X): a = ( 5 * * ( 1 / 2 ) + 1 ) / 2 # Calculate the value of n for X n = int (math.log(( 5 * * ( 1 / 2 )) * X) / math.log(a)) nth = nthFibo(n) nplus = nthFibo(n + 1 ) # Return the nearest # Fibonacci Number if abs (X - nth) < abs (X - nplus): return nth else : return nplus # Function to find the minimum # cost to convert all array # elements to Fibonacci Numbers def getCost(arr): # Stores the total minimum cost cost = 0 # Traverse the given array arr[] for i in arr: # Find the nearest # Fibonacci Number fibo = nearFibo(i) # Add the cost cost + = abs (i - fibo) # Return the final cost return cost # Driver Code arr = [ 56 , 34 , 23 , 98 , 7 ] print (getCost(arr)) |
C#
// C# program to count frequencies of array items using System; class GFG{ // Function to find the // N-th Fibonacci Number static int nthFibo( int n) { // Find the value of a, b, and r double a = (Math.Pow(5, 0.5) + 1) / 2; double b = (-1*(Math.Pow(5, 0.5) ) + 1) / 2; double r = Math.Pow(5, 0.5); // Find the N-th Fibonacci double ans = (Math.Pow(a, n) - Math.Pow(b, n)) / r; // Return the result return ( int )ans; } // Function to find the Fibonacci // number which is nearest to X static int nearFibo( int X) { double a = (Math.Pow(5, 0.5) + 1) / 2; // Calculate the value of n for X int n = ( int )(Math.Log((Math.Pow(5, 0.5)) * X) / Math.Log(a)); int nth = nthFibo(n); int nplus = nthFibo(n + 1); // Return the nearest // Fibonacci Number if (Math.Abs(X - nth) < Math.Abs(X - nplus)) return nth; else return nplus; } // Function to find the minimum // cost to convert all array // elements to Fibonacci Numbers static int getCost( int []arr, int n) { // Stores the total minimum cost int cost = 0; // Traverse the given array arr[] for ( int i = 0; i < n; i++) { // Find the nearest // Fibonacci Number int fibo = nearFibo(arr[i]); // Add the cost cost += Math.Abs(arr[i] - fibo); } // Return the final cost return cost; } // Driver code public static void Main(String []args) { int []arr = { 56, 34, 23, 98, 7 }; int n = arr.Length; Console.WriteLine(getCost(arr, n)); } } // This code is contributed by jana_sayantan |
Javascript
<script> // Javascript program for the above approach // Function to find the // N-th Fibonacci Number function nthFibo(n) { // Find the value of a, b, and r let a = (Math.pow(5, 0.5) + 1) / 2; let b = (-1*(Math.pow(5, 0.5) ) + 1) / 2; let r = Math.pow(5, 0.5); // Find the N-th Fibonacci let ans = (Math.pow(a, n) - Math.pow(b, n)) / r; // Return the result return Math.floor(ans); } // Function to find the Fibonacci // number which is nearest to X function nearFibo(X) { let a = (Math.pow(5, 0.5) + 1) / 2; // Calculate the value of n for X let n = Math.floor(Math.log((Math.pow(5, 0.5)) * X) / Math.log(a)); let nth = nthFibo(n); let nplus = nthFibo(n + 1); // Return the nearest // Fibonacci Number if (Math.abs(X - nth) < Math.abs(X - nplus)) return nth; else return nplus; } // Function to find the minimum // cost to convert all array // elements to Fibonacci Numbers function getCost(arr, n) { // Stores the total minimum cost let cost = 0; // Traverse the given array arr[] for (let i = 0; i < n; i++) { // Find the nearest // Fibonacci Number let fibo = nearFibo(arr[i]); // Add the cost cost += Math.abs(arr[i] - fibo); } // Return the final cost return cost; } // Driver Code let arr = [ 56, 34, 23, 98, 7 ]; let n = arr.length; document.write(getCost(arr, n)); // This code is contributed by _saurabh_jaiswal </script> |
Output:
13
Time Complexity: O(N)
Auxiliary Space: O(1), since no extra space has been taken.
Contact Us