Table of contents
1.
Introduction
2.
Problem Statement
3.
Algorithm
4.
Implementation
4.1.
Code in C++
4.2.
Code in Java
4.3.
Code in Python
4.4.
Complexity Analysis
5.
Frequently Asked Questions 
5.1.
What Type of Data Structure is Priority Queue based on?
5.2.
What is the cost of pushing an element into the Priority Queue?
6.
Conclusion
6.1.
Recommended Problems
Last Updated: Mar 27, 2024
Medium

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

Author Ishita Chawla
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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. Vectorspriority 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

Also Read, Prefix Sum Array

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

example 1

In the first step, we will multiply the element 1 with 6, and the elements will become 6

The minimum element will be 2, 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 - 2 = 8.

So, our answer will be 8

  •      N = 3

A[] = {1, 5000, 9999}

K = 10000

example 2

In the first step, we will multiply 1 by 10000 and it 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.

Array in Python

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

Live masterclass