Flvx's blog

Why doesn't this approach work?
By Flvx, history, 15 months ago, In English

The problem in question is problem and I have solved this using another approach, but I want to know why this two pointer approach does not work. Thanks

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

»
15 months ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

I see every time you are greedily finding the kangaroo with the highest size that can be held by the current kangaroo. There are two wrong things with your code.

  1. If you chose some kangaroo to be held, then you are also considering it to hold some other kangaroo i.e, you are not marking the kangaroos that are held by others and you are considering them to hold new kangaroos.

  2. Even if your code is correct, the approach itself is wrong. You are greedily choosing the kangaroo with the highest weight that can be held. But, the kangaroo you are choosing (to be held) might be fit to hold another kangaroo that cannot be held if you choose to hold this one. For example, consider the kangaroos with the following sizes: 2 3 4 8. You are choosing the kangaroo with size 4 to be held by 8. But after that, 2 and 3 can neither hold nor be held.

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Oh ok, got it. Thanks man :)

    → Reply