Maximize K to make given array Palindrome when each element is replaced by its remainder with K | C ++ program for the above approach ; utility function to calculate the GCD of two numbers ; Function to calculate the largest K , replacing all elements of an array A by their modulus with K , makes A a palindromic array ; check if A is palindrome ; A is not palindromic ; K can be infitely large in this case ; variable to store the largest K that makes A palindromic ; return the required answer ; Driver code ; Input ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int gcd ( int a , int b ) { if ( b == 0 ) return a ; else return gcd ( b , a % b ) ; } int largestK ( int A [ ] , int N ) { int l = 0 , r = N - 1 , flag = 0 ; while ( l < r ) { if ( A [ l ] != A [ r ] ) { flag = 1 ; break ; } l ++ ; r -- ; } if ( flag == 0 ) return -1 ; int K = abs ( A [ 0 ] - A [ N - 1 ] ) ; for ( int i = 1 ; i < N / 2 ; i ++ ) K = gcd ( K , abs ( A [ i ] - A [ N - i - 1 ] ) ) ; return K ; } int main ( ) { int A [ ] = { 1 , 2 , 3 , 2 , 1 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << largestK ( A , N ) << endl ; return 0 ; }