Help needed in HackerEarth problem setter intern hiring challenge Nov 2020

help
#1

Can someone help me with this question? This question is from HackerEarth problem setter intern hiring challenge which is already over.

We are given an array consisting of N elements. We can perform two operations any number of times :

  1. Make any even element E = E/2.
  2. Make any odd element E = 2E.

We have to minimize the maximum absolute difference between any two elements

For ex- N=2 {1,2}

We can make 2–> 2/2 = 1 Thus answer = 0.

Constraints:
1<= T <= 500
2 <=N<= 50000
1<= A[i] <= 1000000
Sum of N over all test cases doesn’t exceed 250000.

#2

Check this.

#3

Both the problems are different. Here we have to minimize the maximum absolute difference between any two elements, in the link you provided the problem is about finding the minimum absolute difference.

#4

Sorry, I didn’t notice that. I thought the approach could somewhat help. Maybe someone else can help you in this.

#5

“https://leetcode.com/contest/weekly-contest-217/problems/minimize-deviation-in-array/”

1 Like
#6

How @ashish_kaur 's link (“https://leetcode.com/discuss/interview-question/376980/Amazon-or-OA-2019-or-Min-Abs-Diff-Between-2-Elements/338921”) is different ? Isn’t it’s same question u asked.

#7

Solution to your problem is based on a very famous algorithm .

Say, the array is [2,10,20,7]

Write all possibilities of each number separately ,

2 = 1,2 …List 1
10 = 10,5…List2
20 = 20,10,5…List3
7 = 7,14…List4

You can see these 4 lists , you have to select one number from each of these lists , and create a final array , which has minimum difference of largest element and smallest element .

Here is how you do it(a famous algorithm) : https://www.techiedelight.com/find-smallest-range-least-one-element-given-lists/

This will always work .

1 Like
#8

That’s what I was looking for. Thank you :slight_smile:

1 Like
#9

Thank you :slight_smile:

#10

Welcome , but clear my doubt , ashish’s question is same or not ?

#11

No…both are different questions…in ashish’s question, we have to modify the array in such a way such that the minimum difference between any two elements is minimum, in my question we have to modify the array in such a way such that the maximum difference between any two elements is minimum.

#12

In ashish’s link : “Determine the minimum absolute difference between any two elements after performing this operation any number of times (possibly zero) on any element of the array.”

then how both question different, and if different then give one example.

#13

For example in the array {2,4,7}, according to Ashish’s question we can modify the array as {2,2,7}, the answer(minimum difference) will be 0 (2 - 2) and according to my problem, we can’t modify the array, hence answer(maximum difference) will be 3 ( 7-4).

1 Like