Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### dunjen_master's blog

By dunjen_master, history, 2 years ago,

You are given an array consisting of N elements. You can perform two operations any no. of times. 1. Make any even element E = E/2. and 2. Make any odd element E = 2E.

You 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

• +12

 » 2 years ago, # |   0 What constraints for N?
•  » » 2 years ago, # ^ |   0 100 test cases and 50000 maximum no of elements
 » 2 years ago, # |   0 for each N there are maximum log2(N)+1 number possible.insert it in a set and keep track of minimum and maximum
•  » » 2 years ago, # ^ |   0 Can you please, elaborate with some pseudo code.
 » 2 years ago, # |   0 At least wait for the contest to be over before asking the solution.
•  » » 2 years ago, # ^ |   0 I thought everybody would have different problems in their set. It was a 1.5 hour test which I have already submitted.
•  » » » 2 years ago, # ^ |   0 But where is the contest?
•  » » » » 2 years ago, # ^ |   0 It is the hackerearth problem setting contest.
 » 22 months ago, # |   0 Can anyone please explain the approach of this question
 » 10 months ago, # |   0 Can someone help me with the approach to this problem?
•  » » 10 months ago, # ^ |   +3 Every no. has 2 states, odd or even. Let's make all no.s odd. Sort the array. Now you can clearly see that the ans would be minimum if we make first few elements of the array even and others as it is. You can check for each case.
•  » » » 7 weeks ago, # ^ |   0 can u plz send me the code i try but i got wrong ans it would be helpful
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +3 I just realized I was wrong in my approach. I wonder why I have upvotes lol. A number can be divided by two multiple times. For example 8 has 4 possible states {8,4,2,1}, So only 2 states thing was wrong. Every number can be be divided by 2, 0 to $log(n)$ times.There must be some solution of this using set/multiset or an appropriate data structure. But without them it can also be solved. Let's say we are given array a[n]. We will first make all the odd numbers even by multiplying by 2. Now, we will never multiply and only divide by 2 , all numbers are their highest states. Let's find minimum of the array. Let us represent it by min. For all numbers other than min, if they are even and dividing them by 2 won't change the min, we should divide them then. Because for the fixed min, it can only decrease max. Once we do this process, let's sort the array in descending order. Let's have 2 pointers mx and mn, representing indexes of max and min element respectively. Initially mx=0 and mn=n-1, So, now we will iterate cyclically in the array from i=0 (at anytime i will represent mx and (i+n-1)%n will represent mn. We will update our answer at each step. So, if we will divide a[i] by 2, it will become new mn. and next i will become mx and if we can't divide it by 2 (it is odd), we will stop because if we can't decrease max element, no point of decreasing other elements. code// Copyright © 2020 Kavish Lodha. All rights reserved. #include using namespace std; #define vll vector #define vvll vector> #define mll map #define max(a,b) ((a>b)?a:b) #define min(a,b) ((a>b)?b:a) #define pb push_back #define prll pair typedef long long ll; typedef long double ld; #define ff first #define ss second #define rep(i,a,n) for(ll i=a; i=a; i--) const ll mod=1e9 + 7; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout<>n; ll a[n]; rep(i,0,n) cin>>a[i]; rep(i,0,n) if(a[i]%2) a[i]*=2; sort(a,a+n); rep(i,1,n){ while(a[i]%2==0&&a[i]>=2*a[0]) a[i]/=2; } sort(a,a+n,greater()); ll ans=a[0]-a[n-1]; ll mx=0,mn=n-1; while(1){ ans=min(ans,a[mx]-a[mn]); if(a[mx]%2==0){ a[mx]/=2; mx=(mx+1)%n; mn=(mn+1)%n; } else break; } cout<
•  » » » » » 7 weeks ago, # ^ |   0 thanks a lot ur explanation and code is great .
 » 7 weeks ago, # |   +1 This exact question is on leetcode. Search Minimise deviation leetcode