dunjen_master's blog

Help in a question

By dunjen_master, history, 5 years ago, In English

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

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What constraints for N?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought everybody would have different problems in their set. It was a 1.5 hour test which I have already submitted.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with the approach to this problem?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        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
        → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

This exact question is on leetcode. Search Minimise deviation leetcode

→ Reply