Minimize the difference

Moderate
0/80
Average time to solve is 45m
profile
Contributed by
0 upvote
Asked in companies
SamsungApple

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?

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

2
4
1 2 3 4 
4
4 3 5 1

Sample Output 1:

1
3

Explanation of Sample Output 1:

Test Case 1: using the operations we can convert the array as follows
[1,2,3,4] -> [2,2,3,2].
Now the maximum difference between any two elements is 1 that is the minimum possible ninja can achieve.

Test Case 2:  using the operations we can convert the array as follows
[4,3,5,1] -> [4,3,5,2].
Now the maximum difference between any two elements is 3 that is the minimum possible ninja can achieve.

Sample Input 2:

2
5 
5 7 8 9 4
4
4 8 16 6

Sample Output 2:

5
1
Hint

Try using a Heap to track the largest number.

Approaches (1)
Greedy technique

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.
Time Complexity

O(N * log(N)), where ‘N’ is the number of elements in the array’.

 

We are iterating all elements one by one and adding an element in MAXHEAP takes O(logN) therefore adding N elements in heaps take O(N * logN).

Space Complexity

O(N), where ‘N’ is the number of elements in the array.
 

We are storing all elements in the MAXHEAP to find the priority of each element.

Code Solution
(100% EXP penalty)
Minimize the difference
Full screen
Console