Minimum Difference Between Maximum and Minimum Value of Array with Given Operations

Ishita Chawla
Last Updated: May 24, 2022
Difficulty Level :
MEDIUM

Introduction

Arrays and strings form the basis of Data Structures and Algorithms, and to solve problems based on these two topics, we often need to use other data structures. Vectors, priority queues, hash tables, stacks, and queues are examples of data structures used to solve such problems. 

This blog will discuss one such problem, finding the minimum difference between the maximum and minimum value of an array with given operations

Problem Statement

You have been provided with an array A[], of size N, and an integer K and are allowed to perform only the following two operations any number of times(possibly zero) on an element of the array:

  • Multiply the element by K.
  • If the element is divisible by K, divide it by K.


Your task is to determine the minimum difference between the minimum and the maximum element of the array.

Example

  •      N = 7

A[] = {1, 2, 4, 5, 6, 8, 10}

K = 6

In the first step, we will multiply the elements 1 and 2 with 6, and the elements will become 6 and 12, respectively. 

The minimum element will be 4, and the maximum will be 10 after this operation. So the minimum difference between the minimum and the maximum element will be equal to 10 - 4 = 6.

So, our answer will be 6

  •      N = 3

A[] = {1, 5000, 9999}

K = 10000

In the first step, we will multiply with 10000 and becomes 10000.

The minimum element will now be 5000, and the maximum element will be 10000. So the minimum difference between the minimum and the maximum element will be equal to 10000 - 5000 = 5000

So, our answer will be 5000.

Algorithm

We will use a priority queue of pairs in order to solve the above problem:

The algorithm has been stated below:

  • All the possible values are first pushed into the priority queue along with the indices, including elements of the array and the values obtained after multiplying the array elements with K and dividing the array elements by K.
  • Now we start popping out the elements one by one. 
  • At every step, check if this popped out value, let's say X having index i, is the maximum and if for all the indices, at least one value has been popped out, the current answer will become X - minimum of (maximum of the previously popped-out values for an index) for all the indices except i. 
  • If the current difference is smaller than what has been computed so far, update the answer.
  • The above steps are repeated until the priority queue becomes empty.

Implementation

Code in C++

// C++ program to find the minimum difference between maximum and minimum value of array with given operations.
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <climits>
using namespace std;
 
// Function to find the minimum difference between maximum and minimum value of array with given operations.
int findMinDif(vector<int> &v, int k)
{
    // Variable to store the result.
    int res = INT_MAX;
 
    // Using a priority queue of pairs to store all the possible values.
    priority_queue<pair<int, int>> p;
 
    // Iterating through all the values and adding to the priority queue.
    for (int i = 0; i < v.size(); i++)
    {
        // In case the number is divisible by k, dividing it and pushing the quotient into the priority queue along with its indexx.
        if (v[i] % k == 0)
            p.push(make_pair(v[i] / k, i));
 
        // Otherwise, pushing the number into the queue as it is along with its index.
        p.push(make_pair(v[i], i));
 
        // Pushing the number into the queue after multiplying it with k.
        p.push(make_pair(v[i] * k, i));
    }
 
    // Hash Map to keep track of the current values.
    unordered_map<int, int> hashMap;
 
    while (!p.empty())
    {
        pair<int, int> topVal = p.top();
        p.pop();
        hashMap.insert(topVal);
 
        // We calculate the answer if for every index there is at least one value.
        if (hashMap.size() == v.size())
        {
            int min_value = INT_MAX;
 
            for (const pair<int, int> &val : hashMap)
                min_value = min(min_value, val.second);
 
            res = min(res, topVal.first - min_value);
        }
    }
 
    // Return the final result.
    return res;
}
int main()
{
    int n, k;
    vector<int> v;
 
    // Taking user input.
    cout << "Enter the total number of elements in the array: \n";
    cin >> n;
    cout << "Enter the elements of the array: \n";
    for (int i = 0; i < n; i++)
    {
        int data;
        cin >> data;
        v.push_back(data);
    }
 
    cout << "Enter the value of K: ";
    cin >> k;
 
    // Calling the function and printing the minimum difference between maximum and minimum value of array with given operations.
    cout << "The minimum difference between maximum and minimum value of array with given operations is " << findMinDif(v, k);
    
    return 0;
}

 

Input

Enter the total number of elements in the array: 
7
Enter the elements of the array:
1 2 4 5 6 8 10
Enter the value of K: 6

Output

The minimum difference between maximum and minimum value of array with given operations is 9

Code in Java

import java.io.*;
import java.util.*;

public class Mindiff {

	/* Main Function */
	private static int calculateMinDifference(int array[], int k)
	{
		int n = array.length;
		/* Variable to store minimum difference */
		int ans = Integer.MAX_VALUE;

		/* PriorityQueue which is used as a multiset to store all possible values */
		PriorityQueue<int[]> pq = new PriorityQueue<>((int x[], int y[]) -> x[0] - y[0]);

		/* Iterate through all the values and then add it to the priority queue */
		for (int i = 0; i < n; i++) {

			/* If the number is divisible by k then divide it by K and add it to the priority queue */
			if (array[i] % k == 0)
				pq.add(new int[] {array[i] / k, i });

			/* Adding number as it is */
			pq.add(new int[] { array[i], i });

			/* Adding number after multiplying */
			pq.add(new int[] { array[i] * k, i });
		}

		HashMap<Integer, Integer> map = new HashMap<>();
		while (!pq.isEmpty()) {
			int temp[] = pq.poll();
			map.put(temp[1], temp[0]);
			/* If every index there is atleast 1 value we calculate the answer */
			if (map.size() == n) {
				ans = Math.min(ans, temp[0] - Collections.min(map.values()));
			}
		}

		return ans;
	}

	/* Main code */
	public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            int n, k;
            int[] v;
         
            // allocating memory for 5 integers.
            
         
            // Taking user input.
            System.out.println("Enter the total number of elements in the array: ");
            n=sc.nextInt();
            v = new int[n];
            System.out.println("Enter the elements of the array: ");
            for (int i = 0; i < n; i++)
            {
                int data;
                data=sc.nextInt();
                v[i]=data;
            }
         
            System.out.print("Enter the value of K: ");
            k=sc.nextInt();
         
            // Calling the function and printing the minimum difference between maximum and minimum value of array with given operations.
            System.out.println("The minimum difference between maximum and minimum value of array with given operations is ");
            System.out.println(calculateMinDifference(v, k));
         
        }
    }

}

 

Input

Enter the total number of elements in the array: 
7
Enter the elements of the array: 
1 2 3 4 5 10 7
Enter the value of K: 5

Output

5

Code in Python

import sys
 
# Function to find Minimum difference between maximum and minimum value from the given array with given operations
 
def calculateMinDiff(arr, k, n):
 
    # Variable to store minimum difference
    result = sys.maxsize
 
    # PriorityQueue, used as a multiset
    # to store all values possible
    heap = []
 
    # Iterate through all the values and
    # add it to the priority queue
    for i in range(n):
        # Adding all three possibilities
        # from current element of the array
 
        if (arr[i] % k == 0):
            heap.append((arr[i] // k, i))
 
        heap.append((arr[i], i))
        heap.append((arr[i] * k, i))
 
    heap.sort()
    heap.reverse()
 
    # HashMap to keep track of current values
 
    mp = {}
 
    while (len(heap) > 0):
 
        temp = heap[0]
        heap.pop(0)
        mp[temp[0]] = temp[1]
 
        # if for every index there is at-least
        # 1 value we calculate the resultwer
        if (len(mp) == n):
 
            min_value = sys.maxsize
 
            for x in mp:
                min_value = min(min_value, mp[x])
 
            result = min(result, temp[0] - min_value - 1)
 
    # Returning the final resultwer
 
    return result

# Size of the array 
n = int(input("Enter the total number of elements in the array: "))

# Input Array 
print("Enter the elements of the array: ")
arr = []
for i in range(0, n):
    element = int(input())
    arr.append(element) 

# K value
k = int(input("Enter the value of K: "))
 
# Printing final output 
print(calculateMinDiff(arr, k, n))

 

Input

Enter the total number of elements in the array: 7
Enter the elements of the array: 
1
2
3
4
5
10
7
Enter the value of K: 5

Output

5

Complexity Analysis

Time Complexity

The time complexity is O(N * log N), where N is the size of the array.

We are pushing elements into the priority queue. The time taken to push an element into the priority queue is O(log N). So,  O(N * log N) gives the time complexity of pushing N elements.

Space Complexity

The space complexity is given by O(N).

We maintain a priority queue to keep track of the elements and the maximum size of the priority queue is O(3 * N) which is approximately equal to O(N).

Conclusion

So, this blog discussed the problem of finding the minimum difference between the maximum and minimum value of array with given operations. To learn more on topics like Arrays and Priority Queues, head over right now to CodeStudio to practice problems and crack your interviews like a Ninja!

Practicing a bunch of questions is not enough in this competitive world. So go check out where you stand among your peers by taking our mock tests and see which areas need improvement.

Feel free to post any type of suggestions in the comments section.

Happy Coding!

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think