Minimize difference by multiplying odds by K and dividing evens by 2
Given an array arr[] of size N and an integer K which is a power of 2. The task is to minimize the difference between the maximum and minimum elements of the array by repeatedly dividing even numbers by 2 and multiplying odd number by K.
Examples:
Input: N = 3, K = 4, arr[] = {1, 2, 6}
Output: 1
Explanation:
- Divide the 3rd element by 2 then elements are 1 2 3.
- Multiply 1st element with 4 then elements are 4 2 3.
- Divide 1st element by 2 then elements are 2 2 3.
So, difference minimum possible is 1.
Input: N = 2, K = 8, arr[] = {1, 8}
Output: 0
Explanation:
- Multiply 1st element by 8 then elements are 8 8.
- Minimum difference possible is 0 here.
Approach: To solve the problem, follow the below idea:
The key idea is to transform odd elements to be comparable to even elements and then efficiently find the minimum difference between the maximum and minimum elements by using a priority queue. The priority queue allows us to iteratively divide the maximum element by 2 while maintaining the order for efficient processing.
Illustration:
Consider example 1: N = 3, K = 4, arr[] = {1, 2, 6}
Currently maximum element is 6 and minimum element is 1. Therefore difference is 6 -1 = 5.
But, we are given some operations. As maximum element is even (divide by 2) and minimum element is odd initially(multiply by k). Hence updated array is {4, 2, 3}.
Now the difference is 4 – 2 = 2. Again if we divide 4 (divide by 2). Updated array {2, 2, 3}.
Minimum difference we achieved: 3 – 2 = 1
Step-by-step algorithm:
- Declare a set.
- Iterate in array:
- if element is odd then add the element into set after multiplying it with k.
- Otherwise add element in set.
- As set will store elements in ascending order:
- Assign minn with first element of set.
- Add all elements in priority queue.
- Iterate in priority queue(Storing elements in Descending order) only if element is even:
- Divide element by 2.
- Update the minimum difference in ans.
- Return ans.
Below is the implementation of the algorithm:
// C++ Implementation
#include <bits/stdc++.h>
using namespace std;
// Function to minimize difference between maximum and
// minimum element
long long minimizeDifference(int n, int k, vector<int>& arr)
{
// Initialize a set
set<long long int> st;
// Iterate in array
for (int i = 0; i < arr.size(); i++) {
// If element is odd
if (arr[i] & 1) {
// Multiply by k
st.insert({ 1ll * k * arr[i] });
}
// if it is even
else {
st.insert({ arr[i] });
}
}
long long int mini = *st.begin();
// Declare a queue
priority_queue<long long int> pq;
// Insert the elements in queue
for (auto it = st.begin(); it != st.end(); it++) {
pq.push(*it);
}
long long int ans = INT_MAX;
// If top element is even
while (pq.top() % 2 == 0) {
// Get the top element
long long int t = pq.top();
pq.pop();
// Divide by 2
t /= 2;
mini = min(mini, t);
// Insert into queue
pq.push(t);
// Update the minimum value
ans = min(ans, pq.top() - mini);
}
// Return the minimum value
return ans;
}
// Driver code
int main()
{
int n = 3;
int k = 4;
vector<int> arr = { 7, 1, 5 };
// Function call
cout << minimizeDifference(n, k, arr);
return 0;
}
import java.util.*;
public class GFG {
// Function to minimize difference between maximum and
// minimum element
public static long minimizeDifference(int n, int k, int[] arr) {
// Initialize a TreeSet (Java's equivalent to C++'s set for sorted unique elements)
TreeSet<Long> st = new TreeSet<>();
// Iterate in array
for (int i = 0; i < n; i++) {
// If element is odd
if (arr[i] % 2 != 0) {
// Multiply by k
st.add((long) arr[i] * k);
}
// if it is even
else {
st.add((long) arr[i]);
}
}
long mini = st.first(); // First element in the sorted set
// Declare a priority queue (max heap)
PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
// Insert the elements in queue
pq.addAll(st);
long ans = Long.MAX_VALUE;
// If top element is even
while (pq.peek() % 2 == 0) {
// Get the top element
long t = pq.poll();
// Divide by 2
t /= 2;
mini = Math.min(mini, t);
// Insert into queue
pq.add(t);
// Update the minimum value
ans = Math.min(ans, pq.peek() - mini);
}
// Return the minimum value
return ans;
}
// Driver code
public static void main(String[] args) {
int n = 3;
int k = 4;
int[] arr = {7, 1, 5};
// Function call
System.out.println(minimizeDifference(n, k, arr));
}
}
import heapq
def minimize_difference(n, k, arr):
# Initialize a set to store unique elements
st = set()
# Iterate over the array
for num in arr:
# If element is odd, multiply by k
if num % 2 != 0:
st.add(num * k)
# Otherwise, add as it is
else:
st.add(num)
mini = min(st) # Find the minimum element in the set
# Create a max heap
pq = [-x for x in st]
# Convert the set to a max heap
heapq.heapify(pq)
ans = float('inf') # Initialize ans to positive infinity
# While the top element is even
while pq[0] % 2 == 0:
# Get the top element
t = -heapq.heappop(pq)
# Divide by 2
t //= 2
# Update the minimum element
mini = min(mini, t)
# Push the updated element to the heap
heapq.heappush(pq, -t)
# Update the answer
ans = min(ans, -pq[0] - mini)
# Return the minimum value
return ans
# Driver code
if __name__ == "__main__":
n = 3
k = 4
arr = [7, 1, 5]
# Function call
print(minimize_difference(n, k, arr))
using System;
using System.Collections.Generic;
class Program
{
// Function to minimize the difference between the maximum and minimum elements
static long MinimizeDifference(int n, int k, List<int> arr)
{
// Initialize a set to store transformed elements
SortedSet<long> st = new SortedSet<long>();
// Iterate through the array
foreach (var num in arr)
{
// If the element is odd, multiply by k and add to the set
if (num % 2 == 1)
{
st.Add(1L * k * num);
}
// If it is even, add to the set
else
{
st.Add(num);
}
}
// Assign minn with the first element of the set
long minn = st.Min;
// Declare a priority queue to store elements in descending order
PriorityQueue<long> pq = new PriorityQueue<long>(st);
long ans = long.MaxValue;
// Iterate in the priority queue only if the element is even
while (pq.Peek() % 2 == 0)
{
// Get the top element
long t = pq.Dequeue();
// Divide by 2
t /= 2;
// Update the minimum difference
ans = Math.Min(ans, pq.Peek() - t);
// Insert the updated value back into the PriorityQueue
pq.Enqueue(t);
}
// Return the minimum difference
return ans;
}
// Driver code
static void Main()
{
// Input values
int n = 3;
int k = 4;
List<int> arr = new List<int> { 1, 2, 6 };
// Function call and print the result
Console.WriteLine(MinimizeDifference(n, k, arr));
}
}
// PriorityQueue class for C#
class PriorityQueue<T> where T : IComparable<T>
{
private List<T> data;
// Constructor to initialize PriorityQueue with given collection
public PriorityQueue(IEnumerable<T> collection)
{
data = new List<T>(collection);
BuildHeap();
}
// Enqueue an item into the PriorityQueue
public void Enqueue(T item)
{
data.Add(item);
int i = data.Count - 1;
while (i > 0)
{
int parent = (i - 1) / 2;
if (data[parent].CompareTo(data[i]) <= 0)
break;
Swap(parent, i);
i = parent;
}
}
// Dequeue the item with the highest priority from the PriorityQueue
public T Dequeue()
{
int last = data.Count - 1;
T frontItem = data[0];
data[0] = data[last];
data.RemoveAt(last);
last--;
int i = 0;
while (true)
{
int leftChild = i * 2 + 1;
int rightChild = leftChild + 1;
int smallestChild = leftChild;
if (rightChild <= last && data[rightChild].CompareTo(data[leftChild]) < 0)
smallestChild = rightChild;
if (leftChild > last || data[i].CompareTo(data[smallestChild]) <= 0)
break;
Swap(i, smallestChild);
i = smallestChild;
}
return frontItem;
}
// Peek at the item with the highest priority in the PriorityQueue
public T Peek()
{
return data.Count > 0 ? data[0] : default(T);
}
// Get the count of items in the PriorityQueue
public int Count
{
get { return data.Count; }
}
// Build the heap by heapifying down from the last non-leaf node to the root
private void BuildHeap()
{
for (int i = data.Count / 2 - 1; i >= 0; i--)
{
HeapifyDown(i);
}
}
// Heapify down from the given index to maintain the heap property
private void HeapifyDown(int i)
{
int leftChild = i * 2 + 1;
int rightChild = leftChild + 1;
int smallestChild = leftChild;
if (rightChild < data.Count && data[rightChild].CompareTo(data[leftChild]) < 0)
smallestChild = rightChild;
if (leftChild < data.Count && data[i].CompareTo(data[smallestChild]) > 0)
{
Swap(i, smallestChild);
HeapifyDown(smallestChild);
}
}
// Swap two elements in the PriorityQueue
private void Swap(int i, int j)
{
T temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
class PriorityQueue {
constructor(comparator) {
this.heap = [];
this.comparator = comparator || ((a, b) => a - b);
}
push(val) {
this.heap.push(val);
this.heap.sort(this.comparator);
}
pop() {
return this.heap.shift();
}
peek() {
return this.heap[0];
}
size() {
return this.heap.length;
}
}
function minimizeDifference(n, k, arr) {
// Initialize a Set (JavaScript's equivalent to Java's TreeSet for sorted unique elements)
let st = new Set();
// Iterate through the array
for (let i = 0; i < n; i++) {
// If the element is odd, multiply by k and add to the set
if (arr[i] % 2 !== 0) {
st.add(arr[i] * k);
}
// If it is even, add to the set as is
else {
st.add(arr[i]);
}
}
// Get the minimum value from the set
let mini = Math.min(...st);
// Declare a priority queue (max heap)
let pq = new PriorityQueue((a, b) => b - a);
// Insert elements from the set into the priority queue
st.forEach(val => pq.push(val));
let ans = Infinity;
// Continue until the top element of the priority queue is odd
while (pq.peek() % 2 === 0) {
// Get the top element
let t = pq.pop();
// Divide the element by 2
t /= 2;
// Update the minimum value
mini = Math.min(mini, t);
// Insert the updated element into the priority queue
pq.push(t);
// Update the answer
ans = Math.min(ans, pq.peek() - mini);
}
// Return the minimum value
return ans;
}
// Driver code
let n = 3;
let k = 4;
let arr = [7, 1, 5];
// Function call
console.log(minimizeDifference(n, k, arr));
Output
3
Time Complexity: O(N* log N), where N is the number of elements in the array arr[].
Auxiliary Space: O(N)
Approach:
We can solve this problem using Mathematical analysis. In which we to follwo the following the steps:
- Firstly, we have to count the number of times we need to divide each even number by 2 to make it odd.
- Then calculate the number of times we need to multiply each odd number by K to make it even.
- Keep track of the min. & max. values obtained after performing the operations
- Lastly, find the difference between the max. & min. values.
Below is the implementation of the algorithm:
#include <iostream>
#include <cmath>
#include <algorithm>
#include <limits> // Include the <limits> header for INT_MAX and INT_MIN
using namespace std;
// Function to minimize the difference
int minimizeDifference(int N, int K, int arr[]) {
int minVal = numeric_limits<int>::max(); // Use numeric_limits<int>::max() to get INT_MAX
int maxVal = numeric_limits<int>::min(); // Use numeric_limits<int>::min() to get INT_MIN
// Iterate through the array
for (int i = 0; i < N; i++) {
int num = arr[i];
// If the number is even
if (num % 2 == 0) {
// Count the number of times we need to divide by 2 to make it odd
int countDivisions = 0;
while (num % 2 == 0) {
num /= 2;
countDivisions++;
}
// Update the minimum value
minVal = min(minVal, countDivisions);
// Update the maximum value
maxVal = max(maxVal, countDivisions);
} else { // If the number is odd
// Calculate the number of times we need to multiply by K to make it even
int countMultiplications = ceil(log(K) / log(2));
// Update the minimum value
minVal = min(minVal, countMultiplications);
// Update the maximum value
maxVal = max(maxVal, countMultiplications);
}
}
// Calculate the difference between the maximum and minimum values
int difference = maxVal - minVal;
return difference;
}
int main() {
// Example usage:
int N = 3;
int K = 4;
int arr[] = {1, 2, 6};
cout << minimizeDifference(N, K, arr) << endl;
return 0;
}
import java.util.Arrays;
public class Main {
public static int minimizeDifference(int N, int K, int[] arr) {
int minVal = Integer.MAX_VALUE;
int maxVal = Integer.MIN_VALUE;
// Iterate through the array
for (int num : arr) {
// If the number is even
if (num % 2 == 0) {
// Count the number of times we need to divide by 2 to make it odd
int countDivisions = 0;
while (num % 2 == 0) {
num /= 2;
countDivisions++;
}
// Update the minimum value
minVal = Math.min(minVal, countDivisions);
// Update the maximum value
maxVal = Math.max(maxVal, countDivisions);
} else { // If the number is odd
// Calculate the number of times we need to multiply by K to make it even
int countMultiplications = (int) Math.ceil(Math.log(K) / Math.log(2));
// Update the minimum value
minVal = Math.min(minVal, countMultiplications);
// Update the maximum value
maxVal = Math.max(maxVal, countMultiplications);
}
}
// Calculate the difference between the maximum and minimum values
int difference = maxVal - minVal;
return difference;
}
public static void main(String[] args) {
// Example usage:
int N = 3;
int K = 4;
int[] arr = {1, 2, 6};
System.out.println(minimizeDifference(N, K, arr));
}
}
import math
def minimize_difference(N, K, arr):
min_val = float('inf')
max_val = float('-inf')
# Iterate through the array
for num in arr:
# If the number is even
if num % 2 == 0:
# Count the number of times we need to divide by 2 to make it odd
count_divisions = 0
while num % 2 == 0:
num //= 2
count_divisions += 1
# Update the minimum value
min_val = min(min_val, count_divisions)
# Update the maximum value
max_val = max(max_val, count_divisions)
else: # If the number is odd
# Calculate the number of times we need to multiply by K to make it even
count_multiplications = math.ceil(math.log2(K))
# Update the minimum value
min_val = min(min_val, count_multiplications)
# Update the maximum value
max_val = max(max_val, count_multiplications)
# Calculate the difference between the maximum and minimum values
difference = max_val - min_val
return difference
# Example usage:
N = 3
K = 4
arr = [1, 2, 6]
print(minimize_difference(N, K, arr))
function minimizeDifference(N, K, arr) {
let minVal = Number.MAX_VALUE;
let maxVal = Number.MIN_VALUE;
// Iterate through the array
for (let num of arr) {
// If the number is even
if (num % 2 === 0) {
// Count the number of times we need to divide by 2 to make it odd
let countDivisions = 0;
while (num % 2 === 0) {
num /= 2;
countDivisions++;
}
// Update the minimum value
minVal = Math.min(minVal, countDivisions);
// Update the maximum value
maxVal = Math.max(maxVal, countDivisions);
} else { // If the number is odd
// Calculate the number of times we need to multiply by K to make it even
let countMultiplications = Math.ceil(Math.log2(K));
// Update the minimum value
minVal = Math.min(minVal, countMultiplications);
// Update the maximum value
maxVal = Math.max(maxVal, countMultiplications);
}
}
// Calculate the difference between the maximum and minimum values
let difference = maxVal - minVal;
return difference;
}
// Example usage:
let N = 3;
let K = 4;
let arr = [1, 2, 6];
console.log(minimizeDifference(N, K, arr));
Output :
1
Time Complexity: O(N*log(K)), where N is the size of the input array and K is the power of 2.
Auxiliary Space: O(1)
Contact Us