Given an array of N elements and you can perform two operations on it:
- Increase any of the array element by X once.
- Decrease any of the array element by X once.
The task is to find the minimum most value of X such that all array elements are equal by either applying operation 1, 2 or not applying any operation. If all the array elements cannot be made equal, then print -1.
Examples:
Input: a[] = {1, 4, 4, 7, 4, 1}
Output: 3
Increase the first and last element by 3.
Decrease the fourth element by 3.Input: {1, 5, 7, 9, 1}
Output: -1
- Increase any of the array element by X once.
- Decrease any of the array element by X once.
- If there are 3 unique elements, if abs(el2-el1) == abs(el3-el2), then the answer is abs(el2-el1). If they are not equal then the answer is -1.
- If there are 2 unique elements, the answer is (el2 – el1) / 2, if el2 – el1 is even, else the answer is (el2 – el1)
- If there is a single unique element, then the answer is 0
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function that returns the // minimum value of X int findMinimumX( int a[], int n) { // Declare a set set< int > st; // Iterate in the array element // and insert them into the set for ( int i = 0; i < n; i++) st.insert(a[i]); // If unique elements is 1 if (st.size() == 1) return 0; // Unique elements is 2 if (st.size() == 2) { // Get both el2 and el1 int el1 = *st.begin(); int el2 = *st.rbegin(); // Check if they are even if ((el2 - el1) % 2 == 0) return (el2 - el1) / 2; else return (el2 - el1); } // If there are 3 unique elements if (st.size() == 3) { // Get three unique elements auto it = st.begin(); int el1 = *it; it++; int el2 = *it; it++; int el3 = *it; // Check if their difference is same if ((el2 - el1) == (el3 - el2)) return el2 - el1; else return -1; } // More than 3 unique elements return -1; } // Driver code int main() { int a[] = { 1, 4, 4, 7, 4, 1 }; int n = sizeof (a) / sizeof (a[0]); cout << findMinimumX(a, n); return 0; } |
Java
// Java implementation of the approach import java.util.HashSet; import java.util.Iterator; import java.util.Set; class GFG { // Function that returns the // minimum value of X static int findMinimumX( int a[], int n) { // Declare a set Set<Integer> st = new HashSet<>(); // Iterate in the array element // and insert them into the set for ( int i = 0 ; i < n; i++) st.add(a[i]); // If unique elements is 1 if (st.size() == 1 ) return 0 ; // Unique elements is 2 if (st.size() == 2 ) { // Get both el2 and el1 Iterator<Integer> it = st.iterator(); int el1 = it.next(); int el2 = it.next(); // Check if they are even if ((el2 - el1) % 2 == 0 ) return (el2 - el1) / 2 ; else return (el2 - el1); } // If there are 3 unique elements if (st.size() == 3 ) { // Get three unique elements Iterator<Integer> it = st.iterator(); int el1 = it.next(); int el2 = it.next(); int el3 = it.next(); // Check if their difference is same if ((el2 - el1) == (el3 - el2)) return el2 - el1; else return - 1 ; } // More than 3 unique elements return - 1 ; } // Driver code public static void main(String[] args) { int a[] = { 1 , 4 , 4 , 7 , 4 , 1 }; int n = a.length; System.out.println(findMinimumX(a, n)); } } // This code is contributed by // Rajnis09 |
Python3
# Python 3 program to implement # the above approach # Function that returns the # minimum value of X def findMinimumX(a, n): # Declare a set st = set () # Iterate in the array element # and insert them into the set for i in range (n): st.add(a[i]) # If unique elements is 1 if ( len (st) = = 1 ): return 0 # Unique elements is 2 if ( len (st) = = 2 ): # Get both el2 and el1 st = list (st) el1 = st[ 0 ] el2 = st[ 1 ] # Check if they are even if ((el2 - el1) % 2 = = 0 ): return int ((el2 - el1) / 2 ) else : return (el2 - el1) # If there are 3 unique elements if ( len (st) = = 3 ): st = list (st) # Get three unique elements el1 = st[ 0 ] el2 = st[ 1 ] el3 = st[ 2 ] # Check if their difference is same if ((el2 - el1) = = (el3 - el2)): return el2 - el1 else : return - 1 # More than 3 unique elements return - 1 # Driver code if __name__ = = '__main__' : a = [ 1 , 4 , 4 , 7 , 4 , 1 ] n = len (a) print (findMinimumX(a, n)) # This code is contributed by # Surendra_Gangwar |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function that returns the // minimum value of X static int findMinimumX( int []a, int n) { // Declare a set List< int > st = new List< int >(); // Iterate in the array element // and insert them into the set for ( int i = 0; i < n; i++) if (!st.Contains(a[i])) st.Add(a[i]); // If unique elements is 1 if (st.Count == 1) return 0; // Unique elements is 2 if (st.Count == 2) { // Get both el2 and el1 int el1 = st[0]; int el2 = st[1]; // Check if they are even if ((el2 - el1) % 2 == 0) return (el2 - el1) / 2; else return (el2 - el1); } // If there are 3 unique elements if (st.Count == 3) { // Get three unique elements int el1 = st[0]; int el2 = st[1]; int el3 = st[2]; // Check if their difference is same if ((el2 - el1) == (el3 - el2)) return el2 - el1; else return -1; } // More than 3 unique elements return -1; } // Driver code public static void Main(String[] args) { int []a = {1, 4, 4, 7, 4, 1}; int n = a.Length; Console.WriteLine(findMinimumX(a, n)); } } // This code is contributed by Princi Singh |
Javascript
// JavaScript program to implement // the above approach // Function that returns the // minimum value of X function findMinimumX(a, n) { // Declare a set let st = new Set() // Iterate in the array element // and insert them into the set for ( var i = 0; i < n; i++) st.add(a[i]) st = Array.from(st) st.sort() // If unique elements is 1 if (st.length == 1) return 0 // Unique elements is 2 if (st.length == 2) { // Get both el2 and el1 let el1 = st[0] let el2 = st[1] // Check if they are even if ((el2 - el1) % 2 == 0) return Math.floor((el2 - el1) / 2) else return (el2 - el1) } // If there are 3 unique elements if (st.length == 3) { // Get three unique elements let el1 = st[0] let el2 = st[1] let el3 = st[2] // Check if their difference is same if ((el2 - el1) == (el3 - el2)) return el2 - el1 else return -1 } // More than 3 unique elements return -1 } // Driver code let a = [1, 4, 4, 7, 4, 1] let n = a.length console.log(findMinimumX(a, n)) // This code is contributed by // phasing17 |
3
Time complexity O(nlogn). Space complexity O(n),because it creates a set of unique elements that could potentially contain all n elements in the input array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!