samedi 8 août 2020

Binary search on two monotonically increasing arrays?

Let's say we have two monotonically increasing arrays

x = 50, 78, 103, 117, 130, 137, 143, 146, 149, 151, 153, 154, 155  
y = 62, 93, 108, 116, 121, 125, 128, 130, 131, 132, 133

Each move of x costs 1 coin and y costs 2 coins.
We need to answer the minimum cost required using both arrays to make sum K.

m1*x + m2*y >= K
where m1 and m2 are number of moves.

For example K=238 then,

  • Minimum number of moves required from x is 5 i.e till 130 which costs 5 * 1 = 5 (cost of each move in x is 1).
  • Minimum number of moves required from y is 3 i.e till 108 which costs 3 * 2 = 6 (cost of each move in y is 2).

This gives us total sum 238 and minimum cost 5 + 6 = 11.

  1. One approach is to use two pointers.
  2. How can I use binary search to solve this kind of question?

Aucun commentaire:

Enregistrer un commentaire