Given an array arr[] of size N, the task is to make all elements equal by applying the operation given below any number of times (possibly zero) to any of the elements in the given array.
- Select an element in the array.
- Reduce it by a positive integer K.
Among all such positive k’s, print the maximum K.
Examples:
Input: arr[] = {3, 7, 5, 3, 3, 7}
Output: 2
Explanation: Choose K = 2, decrement both 7s twice and one 5 once. to get all the elements equal to 3Input: arr[] = {100, -2000, -2000, -2000}
Output: 2100Input: arr[] = {2, 2, 2}
Output: -1
Explanation: As all the elements are already equal hence there can be infinite number of such K possible.
Approach: The task can be solved on the basis of some observations. All the array elements can be made equal to the minimum element of the array. The maximum K can be obtained by finding the greatest common divisor of the adjacent elements in sorted order.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum value of Kint maxValue(int arr[], int N){ // Sorting array of integers sort(arr, arr + N); // Initializing a variable int ans = 0; // Iterating using a for loop for (int i = 1; i < N; i++) { // Find the gcd of ans and // (arr[i] - arr[i - 1]) ans = __gcd(ans, arr[i] - arr[i - 1]); } // Return the answer return ans;}// Driver codeint main(){ // Initializing an array of integers int arr[] = { 3, 7, 5, 3, 3, 7 }; // Number of elements in the array int N = sizeof(arr) / sizeof(int); int ans = maxValue(arr, N); if (ans > 0) cout << ans; else cout << "-1"; return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;import java.math.BigInteger;class GFG { //calculate gcd static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } // Function to find the maximum value of K static int maxValue(int arr[], int N) { // Sorting array of integers Arrays.sort(arr); // Initializing a variable int ans = 0; // Iterating using a for loop for (int i = 1; i < N; i++) { // Find the gcd of ans and // (arr[i] - arr[i - 1]) ans = gcd(ans, arr[i] - arr[i - 1]); } // Return the answer return ans; } // Driver code public static void main (String[] args) { int arr[] = { 3, 7, 5, 3, 3, 7 }; // Number of elements in the array int N = arr.length; int ans = maxValue(arr, N); if (ans > 0) System.out.println(ans); else System.out.println("-1"); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python program for the above approach# calculate gcddef gcd(a, b): return a if b == 0 else gcd(b, a % b);# Function to find the maximum value of Kdef maxValue(arr, N): # Sorting array of integers arr.sort(); # Initializing a variable ans = 0; # Iterating using a for loop for i in range(1,N): # Find the gcd of ans and # (arr[i] - arr[i - 1]) ans = gcd(ans, arr[i] - arr[i - 1]); # Return the answer return ans;# Driver codeif __name__ == '__main__': arr = [3, 7, 5, 3, 3, 7]; # Number of elements in the array N = len(arr); ans = maxValue(arr, N); if (ans > 0): print(ans); else: print("-1");# This code is contributed by shikhasingrajput |
C#
// C# program for the above approachusing System;class GFG { // JavaScript code for the above approach static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Function to find the maximum value of K static int maxValue(int[] arr, int N) { // Sorting array of integers Array.Sort(arr); // Initializing a variable int ans = 0; // Iterating using a for loop for (int i = 1; i < N; i++) { // Find the gcd of ans and // (arr[i] - arr[i - 1]) ans = __gcd(ans, arr[i] - arr[i - 1]); } // Return the answer return ans; } public static void Main() { // Initializing an array of integers int[] arr = { 3, 7, 5, 3, 3, 7 }; // Number of elements in the array int N = arr.Length; int ans = maxValue(arr, N); if (ans > 0) Console.Write(ans); else Console.Write(-1); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach function __gcd(a, b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Function to find the maximum value of K function maxValue(arr, N) { // Sorting array of integers arr.sort(function (a, b) { return a - b }) // Initializing a variable let ans = 0; // Iterating using a for loop for (let i = 1; i < N; i++) { // Find the gcd of ans and // (arr[i] - arr[i - 1]) ans = __gcd(ans, arr[i] - arr[i - 1]); } // Return the answer return ans; } // Driver code // Initializing an array of integers let arr = [3, 7, 5, 3, 3, 7]; // Number of elements in the array let N = arr.length; let ans = maxValue(arr, N); if (ans > 0) document.write(ans); else document.write(-1) // This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(N * logN)
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!
Share your thoughts in the comments
