dunjen_master's blog

Help in a question

By dunjen_master, history, 16 months 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 (11)
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What constraints for N?

→ Reply
»
16 months 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
»
16 months 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
  • »
    »
    16 months 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
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain the approach of this question

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with the approach to this problem?

→ Reply
  • »
    »
    2 months 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