Minimum elements to be inserted in Array to make adjacent differences equal | C ++ program for the above approach ; Function to find gcd of two numbers ; Function to calculate minimum numbers to be inserted to make equal differences between two consecutive elements ; Check if there is only one element in the array then answer will be 0 ; Calculate difference between first and second element of array ; If there is only two elements in the array then gcd of differences of consecutive elements of array will be equal to difference of first and second element of the array ; Loop to calculate the gcd of the differences between consecutive elements of the array ; Loop to calculate the elements to be inserted ; Return the answer ; Driver code
#include <iostream> NEW_LINE using namespace std ; int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } int minimum_elements ( int n , int arr [ ] ) { if ( n < 3 ) return 0 ; int g , ans = 0 , diff , cnt ; diff = arr [ 1 ] - arr [ 0 ] ; g = diff ; for ( int i = 2 ; i < n ; i ++ ) { diff = arr [ i ] - arr [ i - 1 ] ; g = gcd ( g , diff ) ; } for ( int i = 1 ; i < n ; i ++ ) { diff = arr [ i ] - arr [ i - 1 ] ; cnt = diff / g ; ans += ( cnt - 1 ) ; } return ans ; } int main ( ) { int arr [ ] = { 1 , 5 , 8 , 10 , 12 , 16 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << minimum_elements ( n , arr ) ; return 0 ; }