Minimum elements inserted in a sorted array to form an Arithmetic progression | C ++ implementation to find the minimum elements required to be inserted into an array to form an arithmetic progression ; Function to find the greatest common divisor of two numbers ; Function to find the minimum the minimum number of elements required to be inserted into array ; Difference array of consecutive elements of the array ; GCD of the difference array ; Loop to calculate the minimum number of elements required ; Driver Code ; Function calling
#include <bits/stdc++.h> NEW_LINE using namespace std ; int gcdFunc ( int a , int b ) { if ( b == 0 ) return a ; return gcdFunc ( b , a % b ) ; } int findMinimumElements ( int * a , int n ) { int b [ n - 1 ] ; for ( int i = 1 ; i < n ; i ++ ) { b [ i - 1 ] = a [ i ] - a [ i - 1 ] ; } int gcd = b [ 0 ] ; for ( int i = 0 ; i < n - 1 ; i ++ ) { gcd = gcdFunc ( gcd , b [ i ] ) ; } int ans = 0 ; for ( int i = 0 ; i < n - 1 ; i ++ ) { ans += ( b [ i ] / gcd ) - 1 ; } return ans ; } int main ( ) { int arr1 [ ] = { 1 , 6 , 8 , 10 , 14 , 16 } ; int n1 = sizeof ( arr1 ) / sizeof ( arr1 [ 0 ] ) ; cout << findMinimumElements ( arr1 , n1 ) << endl ; }