Minimum number of operations to convert a given sequence into a Geometric Progression | Set 2 | C ++ program for above approach ; Function to find minimum cost ; Sort the array ; Maximum possible common ratios ; Iterate over all possible common ratios ; Calculate operations required for the current common ratio ; Calculate minimum cost ; Driver Code ; Given N ; Given arr [ ] ; Function Calling
#include <bits/stdc++.h> NEW_LINE using namespace std ; void minCost ( int arr [ ] , int n ) { if ( n == 1 ) { cout << 0 << endl ; return ; } sort ( arr , arr + n ) ; float raised = 1 / float ( n - 1 ) ; float temp = pow ( arr [ n - 1 ] , raised ) ; int r = round ( temp ) + 1 ; int i , j , min_cost = INT_MAX ; int common_ratio = 1 ; for ( j = 1 ; j <= r ; j ++ ) { int curr_cost = 0 , prod = 1 ; for ( i = 0 ; i < n ; i ++ ) { curr_cost += abs ( arr [ i ] - prod ) ; prod *= j ; if ( curr_cost >= min_cost ) break ; } if ( i == n ) { min_cost = min ( min_cost , curr_cost ) ; common_ratio = j ; } } cout << min_cost << ' ▁ ' ; cout << common_ratio << ' ▁ ' ; } int main ( ) { int N = 6 ; int arr [ ] = { 1 , 11 , 4 , 27 , 15 , 33 } ; minCost ( arr , N ) ; return 0 ; }