Блог пользователя dunjen_master

Автор dunjen_master, история, 5 лет назад, По-английски

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
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What constraints for N?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

for each N there are maximum log2(N)+1 number possible.insert it in a set and keep track of minimum and maximum

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

At least wait for the contest to be over before asking the solution.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone help me with the approach to this problem?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      can u plz send me the code i try but i got wrong ans it would be helpful

      • »
        »
        »
        »
        3 года назад, # ^ |
        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
»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

This exact question is on leetcode. Search Minimise deviation leetcode