Given an array A[] containing N positive integers, the task is to find the largest possible number K, such that after replacing all elements by the elements modulo K(A[i]=A[i]%K, for all 0<=i<N), the array becomes a palindrome. If K is infinitely large, print -1.
Examples:
Input: A={1, 2, 3, 4}, N=4
Output:
1
Explanation:
For K=1, A becomes {1%1, 2%1, 3%1, 4%1}={0, 0, 0, 0} which is a palindromic array.Input: A={1, 2, 3, 2, 1}, N=5
Output:
-1
Observation: The following observations help in solving the problem:
- If the array is already a palindrome, K can be infinitely large.
- Two numbers, say A and B can be made equal by taking their modulus with their difference(|A-B|) as well as the factors of their difference.
Approach: The problem can be solved by making K equal to the GCD of the absolute differences of A[i] and A[N-i-1]. Follow the steps below to solve the problem:
- Check whether A is already a palindrome. If it is, return -1.
- Store the absolute difference of the first and last elements of the array in a variable, say K, which will store the largest number required to change A into a palindrome.
- Traverse from 1 to N/2-1, and for each current index i, do the following:
- Update K with the GCD of K and the absolute difference of A[i] and A[N-i-1].
- Return K.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// utility function to calculate the GCD of two numbersint gcd(int a, int b){ if (b == 0) return a; else return gcd(b, a % b);}// Function to calculate the largest K, replacing all// elements of an array A by their modulus with K, makes A a// palindromic arrayint largestK(int A[], int N){ // check if A is palindrome int l = 0, r = N - 1, flag = 0; while (l < r) { // A is not palindromic if (A[l] != A[r]) { flag = 1; break; } l++; r--; } // K can be infitely large in this case if (flag == 0) return -1; // variable to store the largest K that makes A // palindromic 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 the required answer return K;}// Driver codeint main(){ // Input int A[] = { 1, 2, 3, 2, 1 }; int N = sizeof(A) / sizeof(A[0]); // Function call cout << largestK(A, N) << endl; return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{// Utility function to calculate the GCD // of two numbersstatic int gcd(int a, int b){ if (b == 0) return a; else return gcd(b, a % b);}// Function to calculate the largest K, // replacing all elements of an array A// by their modulus with K, makes A a// palindromic arraystatic int largestK(int A[], int N){ // Check if A is palindrome int l = 0, r = N - 1, flag = 0; while (l < r) { // A is not palindromic if (A[l] != A[r]) { flag = 1; break; } l++; r--; } // K can be infitely large in this case if (flag == 0) return -1; // Variable to store the largest K // that makes A palindromic int K = Math.abs(A[0] - A[N - 1]); for(int i = 1; i < N / 2; i++) K = gcd(K, Math.abs(A[i] - A[N - i - 1])); // Return the required answer return K;}// Driver codepublic static void main(String[] args){ // Input int A[] = { 1, 2, 3, 2, 1 }; int N = A.length; // Function call System.out.println(largestK(A, N));}}// This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach# utility function to calculate the GCD of two numbersdef gcd(a, b): if (b == 0): return a else: return gcd(b, a % b) # Function to calculate the largest K, replacing all# elements of an array A by their modulus with K, makes A a# palindromic arraydef largestK(A, N): # check if A is palindrome l,r,flag = 0, N - 1, 0 while (l < r): # A is not palindromic if (A[l] != A[r]): flag = 1 break l += 1 r -= 1 # K can be infitely large in this case if (flag == 0): return -1 # variable to store the largest K that makes A # palindromic K = abs(A[0] - A[N - 1]) for i in range(1,N//2): K = gcd(K, abs(A[i] - A[N - i - 1])) # return the required answer return K # Driver codeif __name__ == '__main__': # Input A= [1, 2, 3, 2, 1 ] N = len(A) # Function call print (largestK(A, N))# This code is contributed by mohit kumar 29. |
C#
// c# program for the above approachusing System;using System.Collections.Generic;class GFG{// utility function to calculate the GCD of two numbersstatic int gcd(int a, int b){ if (b == 0) return a; else return gcd(b, a % b);} // Function to calculate the largest K, replacing all// elements of an array A by their modulus with K, makes A a// palindromic arraystatic int largestK(int []A, int N){ // check if A is palindrome int l = 0, r = N - 1, flag = 0; while (l < r) { // A is not palindromic if (A[l] != A[r]) { flag = 1; break; } l++; r--; } // K can be infitely large in this case if (flag == 0) return -1; // variable to store the largest K that makes A // palindromic int K = Math.Abs(A[0] - A[N - 1]); for (int i = 1; i < N / 2; i++) K = gcd(K, Math.Abs(A[i] - A[N - i - 1])); // return the required answer return K;}// Driver codepublic static void Main(){ // Input int []A = { 1, 2, 3, 2, 1 }; int N = A.Length; // Function call Console.Write(largestK(A, N));}}// This code is contributed by ipg2016107. |
Javascript
<script>// Javascript program for the above approach// utility function to calculate the // GCD of two numbersfunction gcd(a, b) { if (b == 0) return a; else return gcd(b, a % b);}// Function to calculate the largest// K, replacing all elements of an // array A by their modulus with K, // makes A a palindromic arrayfunction largestK(A, N){ // Check if A is palindrome let l = 0, r = N - 1, flag = 0; while (l < r) { // A is not palindromic if (A[l] != A[r]) { flag = 1; break; } l++; r--; } // K can be infitely large in this case if (flag == 0) return -1; // Variable to store the largest K // that makes A palindromic let K = Math.abs(A[0] - A[N - 1]); for(let i = 1; i < N / 2; i++) K = gcd(K, Math.abs(A[i] - A[N - i - 1])); // Return the required answer return K;}// Driver code// Inputlet A = [ 1, 2, 3, 2, 1 ];let N = A.length;// Function calldocument.write(largestK(A, N) + "<br>");// This code is contributed by gfgking</script> |
Output
-1
Time Complexity: O(NLogM), where M is the largest element in the array
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
