Minimize deviation of an array by given operations

0 0 5 minutes read

Given an array A[] consisting of positive integers, the task is to calculate the minimum possible deviation of the given arrayA[] after performing the following operations any number of times:

Operation 1: If the array element is even, divide it by 2.
Operation 2: If the array element is odd, multiply it by 2.

The deviation of the array A[] is the difference between the maximum and minimum element present in the array A[].

Examples:

Input: A[] = {4, 1, 5, 20, 3}
Output: 3
Explanation: Array modifies to {4, 2, 5, 5, 3} after performing given operations. Therefore, deviation = 5 – 2 = 3.

Input: A[] = {1, 2, 3, 4}
Output: 1
Explanation: Array modifies to after two operations to {2, 2, 3, 2}. Therefore, deviation = 3 – 2 = 1.

Approach: The problem can be solved based on the following observations:

Even numbers can be divided multiple times until it converts to an odd number.
Odd numbers can be doubled only once as it converts to an even number.
Therefore, even numbers can never be increased.

Follow the steps below to solve the problem:

Traverse the array and double all the odd array elements. This nullifies the requirement for the 2^nd operation.
Now, decrease the largest array element while it’s even.
To store the array elements in sorted manner, insert all array elements into a Set.
Greedily reduce the maximum element present in the Set
If the maximum element present in the Set is odd, break the loop.
Print the minimum deviation obtained.

Below is the implementation of above approach:

C++

// C++ implementation of the
// above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// deviation of the array A[]
void minimumDeviation(int A[], int N)
{
    // Store all array elements
    // in sorted order
    set<int> s;
 
    for (int i = 0; i < N; i++) {
 
        if (A[i] % 2 == 0)
            s.insert(A[i]);
 
        // Odd number are transformed
        // using 2nd operation
        else
            s.insert(2 * A[i]);
    }
 
    // (Maximum - Minimum)
    int diff = *s.rbegin() - *s.begin();
 
    // Check if the size of set is > 0 and
    // the maximum element is divisible by 2
    while ((int)s.size()
           && *s.rbegin() % 2 == 0) {
 
        // Maximum element of the set
        int maxEl = *s.rbegin();
 
        // Erase the maximum element
        s.erase(maxEl);
 
        // Using operation 1
        s.insert(maxEl / 2);
 
        // (Maximum - Minimum)
        diff = min(diff, *s.rbegin() - *s.begin());
    }
 
    // Print the Minimum
    // Deviation Obtained
    cout << diff;
}
 
// Driver Code
int main()
{
    int A[] = { 4, 1, 5, 20, 3 };
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function Call to find
    // Minimum Deviation of A[]
    minimumDeviation(A, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
 
// Function to find the minimum
// deviation of the array A[]
static void minimumDeviation(int A[], int N)
{
   
    // Store all array elements
    // in sorted order
    TreeSet<Integer> s = new TreeSet<Integer>();
    for (int i = 0; i < N; i++) 
    {
 
        if (A[i] % 2 == 0)
            s.add(A[i]);
 
        // Odd number are transformed
        // using 2nd operation
        else
            s.add(2 * A[i]);
    }
 
    // (Maximum - Minimum)
    int diff =  s.last() -  s.first() ;
 
    // Check if the size of set is > 0 and
    // the maximum element is divisible by 2
    while ((s.last() % 2 == 0)) 
    {
 
        // Maximum element of the set
        int maxEl = s.last();
 
        // Erase the maximum element
        s.remove(maxEl);
 
        // Using operation 1
        s.add(maxEl / 2);
 
        // (Maximum - Minimum)
        diff = Math.min(diff, s.last() -  s.first());
    }
 
    // Print the Minimum
    // Deviation Obtained
    System.out.print(diff);
}
 
// Driver code
public static void main(String[] args)
{
    int A[] = { 4, 1, 5, 20, 3 };
    int N = A.length;
 
    // Function Call to find
    // Minimum Deviation of A[]
    minimumDeviation(A, N);
}
}
 
// This code is contributed by susmitakundugoaldanga.

Python3

# Python 3 implementation of the
# above approach
 
# Function to find the minimum
# deviation of the array A[]
def minimumDeviation(A, N):
 
    # Store all array elements
    # in sorted order
    s = set([])
 
    for i in range(N):
        if (A[i] % 2 == 0):
            s.add(A[i])
 
        # Odd number are transformed
        # using 2nd operation
        else:
            s.add(2 * A[i])
 
    # (Maximum - Minimum)
 
    s = list(s)
    diff = s[-1] - s[0]
 
    # Check if the size of set is > 0 and
    # the maximum element is divisible by 2
    while (len(s) and s[-1] % 2 == 0):
 
        # Maximum element of the set
        maxEl = s[-1]
 
        # Erase the maximum element
        s.remove(maxEl)
 
        # Using operation 1
        s.append(maxEl // 2)
 
        # (Maximum - Minimum)
        diff = min(diff, s[-1] - s[0])
 
    # Print the Minimum
    # Deviation Obtained
    print(diff)
 
# Driver Code
if __name__ == "__main__":
    A = [4, 1, 5, 20, 3]
    N = len(A)
 
    # Function Call to find
    # Minimum Deviation of A[]
    minimumDeviation(A, N)
 
    # This code is contributed by chitranayal.

C#

// C# implementation of the
// above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG 
{
     
    // Function to find the minimum
    // deviation of the array A[]
    static void minimumDeviation(int[] A, int N)
    {
       
        // Store all array elements
        // in sorted order
        HashSet<int> s = new HashSet<int>();
        for (int i = 0; i < N; i++) 
        {
            if (A[i] % 2 == 0)
                s.Add(A[i]);
      
            // Odd number are transformed
            // using 2nd operation
            else
                s.Add(2 * A[i]);
        }
        List<int> S = s.ToList();
        S.Sort();
      
        // (Maximum - Minimum)
        int diff = S[S.Count - 1] - S[0];
      
        // Check if the size of set is > 0 and
        // the maximum element is divisible by 2
        while ((int)S.Count != 0 && S[S.Count - 1] % 2 == 0) {
      
            // Maximum element of the set
            int maxEl = S[S.Count - 1];
      
            // Erase the maximum element
            S.RemoveAt(S.Count - 1);
      
            // Using operation 1
            S.Add(maxEl / 2);
             
            S.Sort();
      
            // (Maximum - Minimum)
            diff = Math.Min(diff, S[S.Count - 1] - S[0]);
        }
      
        // Print the Minimum
        // Deviation Obtained
        Console.Write(diff);
    }
 
  // Driver code
  static void Main() 
  {
    int[] A = { 4, 1, 5, 20, 3 };
    int N = A.Length;
  
    // Function Call to find
    // Minimum Deviation of A[]
    minimumDeviation(A, N);
  }
}
 
// This code is contributed by divyeshrabadiya07.

Javascript

<script>
 
 
// JavaScript implementation of the
// above approach
 
// Function to find the minimum
// deviation of the array A[]
function minimumDeviation(A, N)
{
    // Store all array elements
    // in sorted order
    var s = new Set();
 
    for (var i = 0; i < N; i++) {
 
        if (A[i] % 2 == 0)
            s.add(A[i]);
 
        // Odd number are transformed
        // using 2nd operation
        else
            s.add(2 * A[i]);
    }
 
    var tmp = [...s].sort((a,b)=>a-b);
    // (Maximum - Minimum)
    var diff = tmp[tmp.length-1] - tmp[0];
 
    // Check if the size of set is > 0 and
    // the maximum element is divisible by 2
    while (s.size
           && tmp[tmp.length-1] % 2 == 0) {
 
        // Maximum element of the set
        var maxEl = tmp[tmp.length-1];
 
        // Erase the maximum element
        s.delete(maxEl);
 
        // Using operation 1
        s.add(parseInt(maxEl / 2));
        tmp = [...s].sort((a,b)=>a-b);
        // (Maximum - Minimum)
        diff = Math.min(diff, tmp[tmp.length-1] - tmp[0]);
    }
 
    // Print the Minimum
    // Deviation Obtained
    document.write( diff);
}
 
// Driver Code
 
var A = [4, 1, 5, 20, 3];
var N = A.length;
 
// Function Call to find
// Minimum Deviation of A[]
minimumDeviation(A, N);
 
 
</script>

Output:

Time Complexity : O(N * log(N))
Auxiliary Space : O(N)

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 zambiatek!