Given an array arr[] consisting of N positive integers, the task is to minimize the maximum difference between any pair of array elements by multiplying any odd array element by 2 and dividing any even array element by 2.
Examples:
Input: arr[] = {4, 1, 5, 20, 3}
Output: 3
Explanation:
Operation 1: Multiplying arr[1] by 2 modifies arr[] to {4, 2, 5, 20, 3}.
Operation 2: Dividing arr[3] by 2 modifies arr[] to {4, 2, 5, 10, 3}.
Operation 3: Dividing arr[3] by 2 modifies arr[] to {4, 2, 5, 5, 3}.
Therefore, the minimum of the maximum difference of any pair in the array = 5 – 2 = 3.Input: arr[] = {1, 2, 5, 9}
Output: 7
Explanation:
Operation 1: Multiplying arr[0] by 2 modifies arr[] to { 2, 2, 5, 9 }
Operation 2: Multiplying arr[2] by 2 modifies arr[] to {2, 2, 10, 9 }
Therefore, the minimum of the maximum difference of any pair in the array = 9 – 2 = 7.
Approach: Follow the steps below to solve the given problem:
- First, insert all array elements in a Set S. If the array element is even, then insert it as it is. Otherwise, convert it into even by multiplying it by 2.
- Store the difference between the last and first element in the Set S in a variable, say res.
- Traverse the set S in the reverse order and do the following:
- Update the value of res to the maximum of res and the difference between the first and the current element of the set.
- Remove the current element from the Set.
- Insert (current element) / 2 into the set.
- If the value of the current element is odd, then no array more elements can make the maximum difference smaller. Hence break out of the loop.
- After completing the above steps, print the value of res as the resultant difference.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to minimize the maximum// difference between any pair of elements// of the array by the given operationsint minimumMaxDiff(vector<int>& nums){ set<int> s; // Traverse the array for (int i = 0; i < nums.size(); i++) { // If current element is even if (nums[i] % 2 == 0) // Insert it into even s.insert(nums[i]); // Otherwise else // Make it even by multiplying // by 2 and insert it into set s.insert(nums[i] * 2); } // Calculate difference between first // and the last element of the set int res = *s.rbegin() - *s.begin(); // Iterate until difference is minimized while (*s.rbegin() % 2 == 0) { int x = *s.rbegin(); // Erase the current element s.erase(x); // Reduce current element by half // and insert it into the Set s.insert(x / 2); // Update difference res = min(res, *s.rbegin() - *s.begin()); } // Return the resultant difference return res;}// Driver Codeint main(){ vector<int> arr = { 1, 2, 5, 9 }; cout << minimumMaxDiff(arr);} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{ // Function to minimize the maximum // difference between any pair of elements // of the array by the given operations static int minimumMaxDiff(int[] nums) { TreeSet<Integer> s = new TreeSet<Integer>(); // Traverse the array for (int i = 0; i < nums.length; i++) { // If current element is even if (nums[i] % 2 == 0) // Insert it into even s.add(nums[i]); // Otherwise else // Make it even by multiplying // by 2 and insert it into set s.add(nums[i] * 2); } // Calculate difference between first // and the last element of the set int res = s.last() - s.first(); // Iterate until difference is minimized while (s.last() % 2 == 0) { int x = s.last(); // Erase the current element s.remove(x); // Reduce current element by half // and insert it into the Set s.add(x / 2); // Update difference res = Math.min(res, s.last() - s.first()); } // Return the resultant difference return res; } // Driver code public static void main(String[] args) { int[] arr = new int[] { 1, 2, 5, 9 }; System.out.print(minimumMaxDiff(arr)); }}// This code is contributed by jithin |
Python3
# Python3 program for the above approach# Function to minimize the maximum# difference between any pair of elements# of the array by the given operationsdef minimumMaxDiff(nums): s = {} # Traverse the array for i in range(len(nums)): # If current element is even if (nums[i] % 2 == 0): # Insert it into even s[nums[i]] = 1 # Otherwise else: # Make it even by multiplying # by 2 and insert it into set s[nums[i] * 2] = 1 # Calculate difference between first # and the last element of the set sr = list(s.keys()) res = sr[-1] - sr[0] # Iterate until difference is minimized while (list(s.keys())[-1] % 2 == 0): r = list(s.keys()) x = r[-1] # Erase the current element del s[x] # Reduce current element by half # and insert it into the Set s[x // 2] = 1 rr = list(s.keys()) # Update difference res = min(res, rr[-1] - r[0]) # Return the resultant difference return res# Driver Codeif __name__ == '__main__': arr = [ 1, 2, 5, 9 ] print (minimumMaxDiff(arr)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;using System.Linq; class GFG { // Function to minimize the maximum // difference between any pair of elements // of the array by the given operations static int minimumMaxDiff(int[] nums) { HashSet<int> s = new HashSet<int>(); // Traverse the array for (int i = 0; i < nums.Length; i++) { // If current element is even if (nums[i] % 2 == 0) // Insert it into even s.Add(nums[i]); // Otherwise else // Make it even by multiplying // by 2 and insert it into set s.Add(nums[i] * 2); } // Calculate difference between first // and the last element of the set int res = s.Last() - s.First(); // Iterate until difference is minimized while (s.Last() % 2 == 0) { int x = s.Last(); // Erase the current element s.Remove(x); // Reduce current element by half // and insert it into the Set s.Add(x / 2); // Update difference res = Math.Min(res, s.Last() - s.First()); } // Return the resultant difference return res; } // Driver code static public void Main() { int[] arr = new int[] { 1, 2, 5, 9 }; Console.WriteLine(minimumMaxDiff(arr)); }}// This code is contributed by Dharanendra L V |
Javascript
<script>// JavaScript program for the above approach// Function to minimize the maximum// difference between any pair of elements// of the array by the given operationsfunction minimumMaxDiff( nums){ var s = new Set(); // Traverse the array for (var i = 0; i < nums.length; i++) { // If current element is even if (nums[i] % 2 == 0) // Insert it into even s.add(nums[i]); // Otherwise else // Make it even by multiplying // by 2 and insert it into set s.add(nums[i] * 2); } // Calculate difference between first // and the last element of the set var tmp = [...s].sort((a,b)=>a-b) var res = tmp[tmp.length-1] - tmp[0]; // Iterate until difference is minimized while (tmp[tmp.length-1] % 2 == 0) { var x = tmp[tmp.length-1]; // Erase the current element s.delete(x); // Reduce current element by half // and insert it into the Set s.add(parseInt(x / 2)); tmp = [...s].sort((a,b)=>a-b) // Update difference res = Math.min(res,tmp[tmp.length-1] - tmp[0]); } // Return the resultant difference return res;}// Driver Codevar arr = [1, 2, 5, 9];document.write( minimumMaxDiff(arr));</script> |
Output:
7
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!