Minimum increments or decrements by D required to make all array elements equal
Given an array arr[] of size N and an integer D, the task is to make all array elements equal by incrementing or decrementing minimum number of array elements by D. If it is not possible to make all the array elements equal, then print -1.
Examples :
Input: N = 4, d = 2, arr[ ] = {2, 4, 6, 8}
Output: 4
Explanation:
Incrementing arr[0] by D(=2) modifies arr[] to { 4, 4, 6, 8 }.
Decrementing arr[2] by D(=2) modifies arr[] to { 4, 4, 4, 8 }.
Decrementing arr[3] by D(=2) modifies arr[] to { 4, 4, 4, 6 }.
Decrementing arr[3] by D(=2) modifies arr[] to { 4, 4, 4, 4 }.Input: N = 4, K = 3, arr[ ] = {2, 4, 5, 6}
Output: -1
Approach: The idea is to use Greedy Approach to solve this problem. Below are the steps:
- Sort the given array in ascending order.
- Observe that only those array elements can be made equal, whose difference with adjacent indexed element is completely divisible by D, i.e. (a[i + 1] – a[i]) % D == 0.
- If any of the differences is not divisible by D, then print -1 as all the array elements cannot be made equal.
- Now, use a greedy approach here. For minimum operation, consider the mid element and try to change all other elements to mid. Find the number of operations required for the transformation of one number i.e. abs(mid – a[i]) / D.
- In the end, print the minimum number of operations required.
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 minimum count of operations // required to make all array elements equal by // incrementing or decrementing array elements by d void numOperation( int arr[], int N, int D) { // Sort the array sort(arr, arr + N); // Traverse the array for ( int i = 0; i < N - 1; i++) { // If difference between two consecutive // elements are not divisible by D if ((arr[i + 1] - arr[i]) % D != 0) { cout << "-1" ; return ; } } // Store minimum count of operations required to // make all array elements equal by incrementing // or decrementing array elements by d int count = 0; // Stores middle element // of the array int mid = arr[N / 2]; // Traverse the array for ( int i = 0; i < N; i++) { // Update count count += abs (mid - arr[i]) / D; } cout << count; } // Driver Code int main() { // Given N & D int N = 4, D = 2; // Given array arr[] int arr[] = { 2, 4, 6, 8 }; // Function Call numOperation(arr, N, D); } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find minimum count of operations // required to make all array elements equal by // incrementing or decrementing array elements by d static void numOperation( int arr[], int N, int D) { // Sort the array Arrays.sort(arr); // Traverse the array for ( int i = 0 ; i < N - 1 ; i++) { // If difference between two consecutive // elements are not divisible by D if ((arr[i + 1 ] - arr[i]) % D != 0 ) { System.out.println( "-1" ); return ; } } // Store minimum count of operations required to // make all array elements equal by incrementing // or decrementing array elements by d int count = 0 ; // Stores middle element // of the array int mid = arr[N / 2 ]; // Traverse the array for ( int i = 0 ; i < N; i++) { // Update count count += Math.abs(mid - arr[i]) / D; } System.out.println(count); } // Driver code public static void main(String[] args) { // Given N & D int N = 4 , D = 2 ; // Given array arr[] int arr[] = { 2 , 4 , 6 , 8 }; // Function Call numOperation(arr, N, D); } } // This code is contributed by code_hunt. |
Python3
# Python 3 program for the above approach # Function to find minimum count of operations # required to make all array elements equal by # incrementing or decrementing array elements by d def numOperation(arr, N, D): # Sort the array arr.sort() # Traverse the array for i in range (N - 1 ): # If difference between two consecutive # elements are not divisible by D if ((arr[i + 1 ] - arr[i]) % D ! = 0 ): print ( "-1" ) return # Store minimum count of operations required to # make all array elements equal by incrementing # or decrementing array elements by d count = 0 # Stores middle element # of the array mid = arr[N / / 2 ] # Traverse the array for i in range (N): # Update count count + = abs (mid - arr[i]) / / D print (count) # Driver Code if __name__ = = "__main__" : # Given N & D N = 4 D = 2 # Given array arr[] arr = [ 2 , 4 , 6 , 8 ] # Function Call numOperation(arr, N, D) # This code is contributed by chitranayal |
C#
// C# program for the above approach using System; class GFG { // Function to find minimum count of operations // required to make all array elements equal by // incrementing or decrementing array elements by d static void numOperation( int [] arr, int N, int D) { // Sort the array Array.Sort(arr); // Traverse the array for ( int i = 0; i < N - 1; i++) { // If difference between two consecutive // elements are not divisible by D if ((arr[i + 1] - arr[i]) % D != 0) { Console.WriteLine( "-1" ); return ; } } // Store minimum count of operations required to // make all array elements equal by incrementing // or decrementing array elements by d int count = 0; // Stores middle element // of the array int mid = arr[N / 2]; // Traverse the array for ( int i = 0; i < N; i++) { // Update count count += Math.Abs(mid - arr[i]) / D; } Console.WriteLine(count); } // Driver code static public void Main() { // Given N & D int N = 4, D = 2; // Given array arr[] int [] arr = new int [] { 2, 4, 6, 8 }; // Function Call numOperation(arr, N, D); } } // This code is contributed by Dharanendra L V |
Javascript
<script> // Javascript program of the above approach // Function to find minimum count of // operations required to make all // array elements equal by incrementing // or decrementing array elements by d function numOperation(arr, N, D) { // Sort the array arr.sort(); // Traverse the array for (let i = 0; i < N - 1; i++) { // If difference between two consecutive // elements are not divisible by D if ((arr[i + 1] - arr[i]) % D != 0) { document.write( "-1" ); return ; } } // Store minimum count of operations // required to make all array elements // equal by incrementing or decrementing // array elements by d let count = 0; // Stores middle element // of the array let mid = arr[N / 2]; // Traverse the array for (let i = 0; i < N; i++) { // Update count count += Math.abs(mid - arr[i]) / D; } document.write(count); } // Driver Code // Given N & D let N = 4, D = 2; // Given array arr[] let arr = [ 2, 4, 6, 8 ]; // Function Call numOperation(arr, N, D); // This code is contributed by chinmoy1997pal </script> |
4
Time Complexity: O(N * Log(N))
Auxiliary Space: O(1)
Contact Us