Minimum number of operations to convert a given sequence into a Geometric Progression | C ++ program to find minimum number of operations to convert a given sequence to an Geometric Progression ; Function to print the GP series ; Check for possibility ; Function for getting the Arithmetic Progression ; The array c describes all the given set of possible operations . ; Size of c ; candidate answer ; loop through all the permutations of the first two elements . ; a1 and a2 are the candidate first two elements of the possible GP . ; temp stores the current answer , including the modification of the first two elements . ; common ratio of the possible GP ; To check if the chosen set is valid , and id yes find the number of operations it takes . ; ai is value of a [ i ] according to the assumed first two elements a1 , a2 ith element of an GP = a1 * ( ( a2 - a1 ) ^ ( i - 1 ) ) ; Check for the " proposed " element to be only differing by one ; set the temporary ans ; to infinity and break ; update answer ; Calling function to print the sequence ; Driver Code ; array is 1 - indexed , with a [ 0 ] = 0 for the sake of simplicity ; Function to print the minimum operations and the sequence of elements
#include <bits/stdc++.h> NEW_LINE using namespace std ; void construct ( int n , pair < double , double > ans_pair ) { if ( ans_pair . first == -1 ) { cout << " Not ▁ possible " ; return ; } double a1 = ans_pair . first ; double a2 = ans_pair . second ; double r = a2 / a1 ; cout << " The ▁ resultant ▁ sequence ▁ is : STRNEWLINE " ; for ( int i = 1 ; i <= n ; i ++ ) { double ai = a1 * pow ( r , i - 1 ) ; cout << ai << " ▁ " ; } } void findMinimumOperations ( double * a , int n ) { int ans = INT_MAX ; int c [ ] = { -1 , 0 , 1 } ; int possibilities = 3 ; int pos1 = -1 , pos2 = -1 ; for ( int i = 0 ; i < possibilities ; i ++ ) { for ( int j = 0 ; j < possibilities ; j ++ ) { double a1 = a [ 1 ] + c [ i ] ; double a2 = a [ 2 ] + c [ j ] ; int temp = abs ( a1 - a [ 1 ] ) + abs ( a2 - a [ 2 ] ) ; if ( a1 == 0 a2 == 0 ) continue ; double r = a2 / a1 ; for ( int pos = 3 ; pos <= n ; pos ++ ) { double ai = a1 * pow ( r , pos - 1 ) ; if ( a [ pos ] == ai ) { continue ; } else if ( a [ pos ] + 1 == ai a [ pos ] - 1 == ai ) { temp ++ ; } else { temp = INT_MAX ; break ; } } if ( temp < ans ) { ans = temp ; pos1 = a1 ; pos2 = a2 ; } } } if ( ans == -1 ) { cout << " - 1" ; return ; } cout << " Minimum ▁ Number ▁ of ▁ Operations ▁ are ▁ " << ans << " STRNEWLINE " ; pair < double , double > ans_pair = { pos1 , pos2 } ; construct ( n , ans_pair ) ; } int main ( ) { double a [ ] = { 0 , 7 , 20 , 49 , 125 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; findMinimumOperations ( a , n - 1 ) ; return 0 ; }