Find minimum number of steps to collect target number of coins

user_17293622 0
Viewed 681

Given a list of n houses, each house has a certain number of coins in it. And a target value t. We have to find the minimum number of steps required to reach the target.
The person can choose to start at any house and then go right or left and collect coins in that direction until it reaches the target value. But the person cannot
change the direction.
Example: 5 1 2 3 4 These are supposed the coin values in 5 houses
and the target is 13 then the minimum number of steps required is 5 because we have to select all the coins.

My Thoughts:
One way will be for each index i calculate the steps required in left or right direction
to reach the target and then take the minimum of all these 2*n values.
Could there be a better way ?

algorithm
1 Answers

First, let's simplify and canonize the problem.

Observation 1: The "choose direction" capability is redundant, if you choose to go from house j to house i, you can also go from i to j to have the same value, so it is sufficient to look at one direction only.

Observation 2: Now that we can look at the problem as going from left to right (observation 1), it is clear that we are looking for a subarray whose value exceeds k.

This means that we can canonize the problem:

Given an array with non negative values a, find minimal subarray with values summing k or more.

There are various ways to solve this, one simple solution using a sorted map (balanced tree for example) is to go from left to right, summing values, and looking for the last element seen whose value was sum - k.

Pseudo code:

solve(array, k):
  min_houses = inf
  sum = 0
  map = new TreeMap()
  map.insert(0, -1)  // this solves issue where first element is sufficient on its own.
  for i from 0 to array.len():
    sum = sum + array[i]
    candidate = map.FindClosestLowerOrEqual(sum - k)
    if candidate == null:  // no matching sum, yet
      continue
    min_houses = min(min_houses, i - candidate)
    map.insert(sum, i)
  return min_houses

This solution runs in O(nlogn), as each map insertion takes O(logn), and there are n+1 of those.

An optimization, running in O(n), can be done if we take advantage of "non negative" trait of the array. This means, as we go on in the array - the candidate chosen (in the map seek) is always increasing.

We can utilize it to have two pointers running concurrently, and finding best matches, instead of searching from scratch in the index as we did before.

solve(array, k):
  left = 0
  sum = 0
  min_houses = infinity
  for right from 0 to len(array):
    sum = sum + array[right]
    while (left < right && sum >= k):
      min_houses = min(min_houses, right - left)
      sum = sum - array[left]
      left = left + 1
  return min_houses

This runs in O(n), as each index is increased at most n times, and every operation is O(1).

user_5726700
Related