Last Updated: 8 Apr, 2021

Minimize the difference

Moderate

Asked in companies

Solve now

Problem statement

Ninja has an array and he can perform two operations any number of times.

Operation 1: He can divide any even element by 2
For example: [1, 2, 3, 4, 5] -> [1, 1, 3, 2, 5]

Operation 2: He can multiple any odd element by 2:
For example: [1, 2, 3, 4, 5] -> [2, 2, 6, 4, 5]

Ninja wants your help to minimize the maximum difference between any two elements in the array using these operations.

Can you help Ninja achieve this task?

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array.

The second line of each test case contains ‘N’ space-separated integers representing the array elements.

Output Format :

For each test case, print a single line containing a single integer denoting the minimum of the maximum difference of any two elements.

The output for each test case is printed in a separate line.

Constraints :

1 <= T <= 5
1 <= N <= 5000
1 <= ARR[i] <= 109

Where ‘T’ is the number of test cases, ‘N’ is the number of elements and ‘ARR[i]’ represents the element of the array.

Time limit: 1 second

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

The idea here is to remove one of the operations and then using some observations we can find the answer.

Observation 1: We can double odd numbers once only and can divide even numbers as many times as possible and get an odd number.

Observation 2: We can never increase an even number using any operation.

Using observation 1 we can say that if we perform operation 2 on every odd element then we don’t need to consider this operation and convert all numbers to even numbers.

Now, we just need to put all elements into a MAXHEAP and track the smallest element, till we don’t get our top element as odd we will continuously pop one element and push back its half value. And checking for minimum value in each step.

Algorithm:

Declare a MAXHEAP and a variable RES.
for( i : 0 -> ARR.size() )
- if(ARR[i] is odd)
  - MAXHEAP.push(ARR[i] * 2)
- else
  - MAXHEAP.push(ARR[i] )
Declare a variable ‘MINARR’ = int max
While(MAXHEAP.top() is even)
- Int t = MAXHEAP.top
- MAXHEAP.pop
- MAXHEAP.push(t/2)
- MINARR = min(t/2, minARR)
- RES = MAXHEAP.top - minARR
Return RES.

Solve now