Make all elements of an Array equal by adding or subtracting at most K
Given an array arr[] containing positive integers of size N and an integer K, the task is to make all the elements in the array equal to some value D (D > 0) such that |arr[i] – D| ? K. Print the value of D or -1 if it is not possible to make the array equal.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}, K = 2
Output: 3
Explanation:
All the elements in the array can be made equal to 3 as:
|arr[0] – 3| = 2 ? 2
|arr[1] – 3| = 1 ? 2
|arr[2] – 3| = 0 ? 2
|arr[3] – 3| = 1 ? 2
|arr[4] – 3| = 2 ? 2
Input: arr[] = {1, 6, 20}, K = 1
Output: -1
Explanation:
It is not possible to equalize the array
Approach: The idea is to first find the minimum element of the array.
- If M is the minimum element of the array, then M + K is the maximum possible value which this minimum element can take in order to satisfy the condition arr[i] – D ? K.
- Then, D = M + K, if for all the elements in the array, (M + K) lies in the range [arr[i] – K, arr[i] + K].
- Therefore, we simply iterate over every element in the array and check for this condition.
Below is the implementation of the above approach:
C++
// C++ program to make all elements // of an Array equal by adding or // subtracting at most K #include <bits/stdc++.h> using namespace std; // Function to equalize the array by // adding or subtracting at most K // value from each element int equalize( int arr[], int n, int k) { // Finding the minimum element // from the array int min_ele = *min_element(arr, arr + n); // Boolean variable to check if the // array can be equalized or not bool flag = true ; // Traversing the array for ( int i = 0; i < n; i++) { // Checking if the values lie // within the possible range // for each element if (!((arr[i] + k) >= min_ele + k && min_ele + k >= (arr[i] - k))) { // If any value doesn't lie in // the range then exit the loop flag = false ; break ; } } if (flag) { // Value after equalizing the array return min_ele + k; } // Array cannot be equalized else return -1; } // Driver code int main() { int K = 2; int arr[] = { 1, 2, 3, 4, 5 }; int N = sizeof (arr) / sizeof (arr[0]); cout << equalize(arr, N, K); } |
Java
// Java program to make all elements // of an Array equal by adding or // subtracting at most K import java.util.*; class GFG{ // Function to equalize the array by // adding or subtracting at most K // value from each element static int equalize( int arr[], int n, int k) { // Finding the minimum element // from the array int min_ele = Arrays.stream(arr).min().getAsInt(); // Boolean variable to check if the // array can be equalized or not boolean flag = true ; // Traversing the array for ( int i = 0 ; i < n; i++) { // Checking if the values lie // within the possible range // for each element if (!((arr[i] + k) >= min_ele + k && min_ele + k >= (arr[i] - k))) { // If any value doesn't lie in // the range then exit the loop flag = false ; break ; } } if (flag) { // Value after equalizing the array return min_ele + k; } // Array cannot be equalized else return - 1 ; } // Driver code public static void main(String[] args) { int K = 2 ; int arr[] = { 1 , 2 , 3 , 4 , 5 }; int N = arr.length; System.out.print(equalize(arr, N, K)); } } // This code is contributed by Princi Singh |
Python3
# Python program to make all elements # of an Array equal by adding or # subtracting at most K # Function to equalize the array by # adding or subtracting at most K # value from each element def equalize(arr, n, k): # Finding the minimum element # from the array min_ele = min (arr); # Boolean variable to check if the # array can be equalized or not flag = True ; # Traversing the array for i in range (n): # Checking if the values lie # within the possible range # for each element if ( not ((arr[i] + k) > = (min_ele + k) and (min_ele + k) > = (arr[i] - k))) : # If any value doesn't lie in # the range then exit the loop flag = False ; break ; if (flag): # Value after equalizing the array return min_ele + k; # Array cannot be equalized else : return - 1 ; # Driver code if __name__ = = '__main__' : K = 2 ; arr = [ 1 , 2 , 3 , 4 , 5 ] ; N = len (arr) print (equalize(arr, N, K)) # This code is contributed by Princi Singh |
C#
// C# program to make all elements // of an Array equal by adding or // subtracting at most K using System; using System.Linq; class GFG{ // Function to equalize the array by // adding or subtracting at most K // value from each element static int equalize( int []arr, int n, int k) { // Finding the minimum element // from the array int min_ele = arr.Min(); // Boolean variable to check if the // array can be equalized or not bool flag = true ; // Traversing the array for ( int i = 0; i < n; i++) { // Checking if the values lie // within the possible range // for each element if (!((arr[i] + k) >= min_ele + k && min_ele + k >= (arr[i] - k))) { // If any value doesn't lie in // the range then exit the loop flag = false ; break ; } } if (flag) { // Value after equalizing the array return min_ele + k; } // Array cannot be equalized else return -1; } // Driver code public static void Main(String[] args) { int K = 2; int []arr = { 1, 2, 3, 4, 5 }; int N = arr.Length; Console.Write(equalize(arr, N, K)); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program to make all elements // of an Array equal by adding or // subtracting at most K // Function to equalize the array by // adding or subtracting at most K // value from each element function equalize(arr, n, k) { // Finding the minimum element // from the array let min_ele = arr.sort((a, b) => a - b)[0]; // Boolean variable to check if the // array can be equalized or not let flag = true ; // Traversing the array for (let i = 0; i < n; i++) { // Checking if the values lie // within the possible range // for each element if (!((arr[i] + k) >= min_ele + k && min_ele + k >= (arr[i] - k))) { // If any value doesn't lie in // the range then exit the loop flag = false ; break ; } } if (flag) { // Value after equalizing the array return min_ele + k; } // Array cannot be equalized else return -1; } // Driver code let K = 2; let arr = [ 1, 2, 3, 4, 5 ]; let N = arr.length; document.write(equalize(arr, N, K)); // This code is contributed by _saurabh_jaiswal </script> |
3
Time Complexity: O(n), to traverse the array where n is the size of the given array
Auxiliary Space: O(1), as no extra space is used
Contact Us