Minimum elements inserted in a sorted array to form an Arithmetic progression | Java 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
class GFG { static int gcdFunc ( int a , int b ) { if ( b == 0 ) return a ; return gcdFunc ( b , a % b ) ; } static int findMinimumElements ( int [ ] a , int n ) { int [ ] b = new int [ 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 ; } public static void main ( String [ ] args ) { int arr1 [ ] = { 1 , 6 , 8 , 10 , 14 , 16 } ; int n1 = arr1 . length ; System . out . print ( findMinimumElements ( arr1 , n1 ) + "NEW_LINE"); } }