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 :
- Make any even element E = E/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.
1 Like
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.
Sorry, I didn’t notice that. I thought the approach could somewhat help. Maybe someone else can help you in this.
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) : Find the smallest range with at least one element from each of the given lists | Techie Delight
This will always work .
1 Like
That’s what I was looking for. Thank you 
1 Like
Welcome , but clear my doubt , ashish’s question is same or not ?
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.
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.
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
hi,is questions in problem setter test remains same?cause i also gave the test 20 days before and same question asked,
Please send the full code for hackeearth question. I am unable to get the approach.