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;
}

You can also try this code with Online C++ Compiler
Run Code
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 8
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));
}
}
}

You can also try this code with Online Java Compiler
Run Code
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
7
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))

You can also try this code with Online Python Compiler
Run Code
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
7
Complexity Analysis
Time Complexity
The time complexity is O(N * log N), where N is the size of the array.
We are pushing N 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).4
Check out this problem - Next Smaller Element
Frequently Asked Questions
What Type of Data Structure is Priority Queue based on?
Priority Queue is based on the Heap Data Structure.
What is the cost of pushing an element into the Priority Queue?
O(logN) where N is the number of elements.
Conclusion
In this blog, we discussed the problem of finding the minimum difference between the maximum and minimum value of an array with given operations. We discussed the priority queue which is an important data structure that is used widely. To learn more on topics like Arrays and Priority Queues, head over right now to Coding Ninjas Studio to practice problems and crack your interviews like a Ninja!
Recommended Problems
To gain an edge over the competition check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, and some Interview Experiences as well as Contests and Interview Bundles only on Coding Ninjas Studio.
Feel free to post any type of suggestions in the comments section.
Happy Coding!