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 Xint 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 codeint 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 approachimport 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 Xdef 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 codeif __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 approachusing 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 Xfunction 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 codelet a = [1, 4, 4, 7, 4, 1]let n = a.lengthconsole.log(findMinimumX(a, n))// This code is contributed by// phasing17 |
Output
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.
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!
