Minimum number of operations required

Question

I came across this question in recent interview :

Given an array of integers and an integer k. You can perform operations any number of times(may be zero) on any number of elements in an array :

If number is divisible by k, divide it by k (you are not allowed to multiply it by k if it is divisible)

If number is not divisible by k, multiply it by k

You need to update this array in such a way that difference between maximum and minimum number in an array is minimum and find minimum number of operations to do so.

e.g. Let a[5] = {82, 79, 38, 49, 9} and k=5, we apply 2nd operation on last element. Now, a[5] = {82, 79, 38, 49, 9*5} and this updated array gives minimum difference between minimum and maximum numbers i.e. max - min = 82 - 38 = 44

I am thinking about applying recursive solution fixing one number and trying to keep all numbers as close as fixed number.

But need better approach to solve this problem efficiently. Thanks in advance.

user_8112138 · Answer

This is doable in O(NlogN). For each element we can write out every element it can transform into. So let each element transform into a list of candidate elements it can become. The problem now becomes smallest range covering elements from k lists which can be done in O(NlogN).

A really simple way to solve the smallest range problem:

Merge the elements from each list into one list, keep track of the list that each element came from
Run a sliding window over the merged list that has one element from each sublist
Take candidate ranges

The following is my solution to the smallest range problem. You just need some boilerplate code to transform your list of integers into a list of lists.

from collections import deque, Counter

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:

        new = []
        # merge each list and keep track of original list
        for i in range(len(nums)):
            for j in nums[i]:
                new.append((j, i))
        # sort so each sliding window represents a range
        new.sort()

        d = deque()
        c = Counter()

        res = [-float('inf'), float('inf')]
        # iterate over sliding windows that contain each list
        for i in new:
            d.append(i)
            c[i[1]] += 1
            while len(c) == len(nums):
                res = min(res, [d[0][0], d[-1][0]], key = lambda x: x[1] - x[0])
                a, b = d.popleft()
                c[b] -= 1
                if not c[b]: del c[b]
        return res

Minimum number of operations required

1 Answers