CODEWITHSUNDEEP
arraysalgorithmlanguage-agnostic
Prateek Surana
Prateek Surana

Reputation: 692

Find minimum number of operations on to empty an array

I recently faced a problem in an interview in which I was given a size of a crocodile and an array representing the size of fishes in a pond. The crocodile can eat the fishes less than its size and every time it eats that fish its size gets increases by the size of that fish. We can perform two types operations on the array any number of times.

  1. Remove any fish from the pond
  2. Add fish of any size to the pond

Given the initial size of the crocodile and the array of fishes in the pond, we have to find the minimum no. of such operations so as to empty the array representing the pond.

For eg -

The initial size of the crocodile is 20 and the array of fishes is

[10,15,20,30,100]

In this case the crocodile eats all the fishes except the 100 and its size becomes 85 so one of the solution might be removing the fish with size 100. So the output will be 1.

What is the best possible algorithm to implement the above problem, can it be solved recursively?

Upvotes: 0

Views: 589

Answers (1)

Maras
Maras

Reputation: 982

So first of all, sort the array. The crocodile will eat each fish that is smaller than him. Start from the left, if the crocodile can eat the fish, increase his size. If there is no fish left, return 0. If not, make two variables, a potential result = infinity and actions = 0. One of the possible answers is deleting the rest of the fish. Set result as minimum(result, fish_left + actions). Then try to add new fish. You always want the crocodile to grow as big as possible, so insert a fish that size is 1 less than the crocodile's (multiply it's size by 2 and decrease by 1). Increase actions by one. Let the crocodile eat all possible fish. Repeat until all fish are eaten, then return result. If the numbers are really big, you may end up adding tons of fish, so how do we overcome it? Well, your minimum answer so far is result. If you ever make more actions than your current result, you can't get a better one, so you can end the loop and return result. So our complexity is O (n) - size of an array. Can't imagine a faster one. EDIT: Actually O (n log n) because of sort. And you can do everything recursively (literally everything), but I don't really see the point in doing it here.

Upvotes: 2

Related Questions