We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count All Possible Routes

Number: 1680

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an array of distinct integers representing city locations, and integers start, finish, and fuel, the task is to count all possible routes from the start city to the finish city while consuming fuel. Moving from city i to city j uses |locations[i] - locations[j]| fuel units, and you are allowed to visit the same city multiple times. If the fuel runs out (fuel < 0), the route is invalid. Since the result can be large, return the answer modulo 10^9+7.

Key Insights

  • Use dynamic programming to count the number of ways to reach the finish city.
  • States are defined by the current city and the remaining fuel.
  • Recur for each city reachable from the current city if the required fuel is available.
  • Leverage memoization to avoid recalculating results for the same (city, fuel left) state.
  • The result is accumulated by counting the current city if it is the finish city, plus routes from potential next moves.

Space and Time Complexity

Time Complexity: O(n * fuel * n) = O(n^2 * fuel) where n is the number of cities, because for each state (city, fuel) we might explore all other cities.
Space Complexity: O(n * fuel) for the DP (memoization) table.

Solution

The approach is to perform a depth-first search (DFS) using recursion with memoization. We define a recursive function that returns the number of routes from the current city with a given amount of fuel left. At each recursion step, we:

  1. Check if the result has been computed before (memoized) for the current state.
  2. Initialize a counter which is incremented if the current city is the finish city.
  3. Iterate over all cities and for each move that can be performed without the fuel dropping below zero, recursively calculate the routes from that city with the updated fuel amount.
  4. Sum up all counts and take modulo 10^9+7. The result of the initial call from the start city with full fuel is returned.

Code Solutions

# Define the modulo constant
MOD = 10**9 + 7

def countRoutes(locations, start, finish, fuel):
    # Cache for memoization: key as (curr_city, remaining_fuel)
    memo = {}
    
    def dfs(city, fuel_left):
        # If the state has been computed, return it
        if (city, fuel_left) in memo:
            return memo[(city, fuel_left)]
        
        # Start count. If current city is finish, count one valid route.
        count = 1 if city == finish else 0
        
        # Try moving to every other city if fuel is sufficient.
        for next_city in range(len(locations)):
            if next_city != city:
                cost = abs(locations[city] - locations[next_city])
                if fuel_left >= cost:
                    count = (count + dfs(next_city, fuel_left - cost)) % MOD
        
        # Memoize and return the computed value.
        memo[(city, fuel_left)] = count
        return count

    return dfs(start, fuel)

# Example usage:
# locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
# Expected Output: 4
print(countRoutes([2,3,6,8,4], 1, 3, 5))
← Back to All Questions