FastPrepCompute Number of Locations
Problems/Compute Number of Locations

Compute Number of Locations

Money Forward logoMoney Forward● HardOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

You want to buy a car and will drive it around N locations, numbered 1 to N. There are M roads. Road j is given as roads[j] = [u, v, d]: it connects locations u and v in both directions and has length d.

The car's fuel tank holds L units of fuel, and driving 1 unit of distance uses 1 unit of fuel. You live at location 1 and start there with a full tank.

Some locations have a gas station: g[i - 1] = 1 if location i has one, and g[i - 1] = 0 if it does not. Location 1 always has one. When you reach a location with a gas station, you can fill the tank back up to L. You may refuel at any station as many times as you like, and reaching a station with exactly 0 fuel left is fine. You must never run out of fuel before reaching the next location.

A location counts as visitable if you can drive from location 1 to it and then back to location 1 without running out of fuel. You may take any route. Location 1 itself counts. Return the number of visitable locations.

Function

computeNumberOfLocations(N: int, M: int, L: int, g: int[], roads: int[][]) → int

Complete the function computeNumberOfLocations in the editor.

computeNumberOfLocations has the following parameters:

  1. int N: the number of locations
  2. int M: the number of roads
  3. int L: the fuel tank capacity
  4. int[] g: g[i - 1] is 1 if location i has a gas station, else 0
  5. int[][] roads: M rows [u, v, d], one per road

The function returns an int: the number of locations you can visit and come back home from without running out of fuel.

Examples

Example 1

N = 6M = 6L = 10g = [1, 0, 0, 1, 0, 0]roads = [[1, 2, 4], [1, 3, 6], [2, 4, 5], [3, 6, 3], [4, 5, 5], [5, 6, 8]]return = 4

Locations 1 and 4 have gas stations, and the tank holds 10.

  • Location 1 is home, so it counts.
  • Location 2 is 4 away from home: 4 there and 4 back uses 8 ≤ 10 fuel. It counts.
  • Location 4 is 9 away (1 → 2 → 4). You arrive with 1 fuel left, refill, and drive back the same way. It counts.
  • Location 5 is 5 away from the station at 4: 5 there and 5 back uses exactly 10. It counts.
  • Location 3 is 6 away from home, and every other station is farther. A round trip needs 12 > 10 fuel, so it does not count.
  • Location 6 is 9 from home (1 → 3 → 6) and 13 from station 4 (4 → 5 → 6). Neither round trip fits in 10, so it does not count.

The visitable locations are 1, 2, 4 and 5, so the answer is 4.

Constraints

  • 2 ≤ N ≤ 105
  • 1 ≤ M ≤ 105
  • roads.length = M and each roads[j] has exactly 3 numbers [u, v, d]
  • g.length = N
  • 1 ≤ L ≤ 109
  • g[i] is 0 or 1, and g[0] = 1
  • 1 ≤ u < v ≤ N for every road
  • 1 ≤ d ≤ 106 for every road
  • Roads are sorted by their first location: roads[j][0] ≤ roads[j + 1][0].
  • No two roads connect the same pair of locations.
  • Every location can be reached from location 1 by roads.
  • Route lengths can reach about 1011, so add distances in 64-bit integers.

More Money Forward interview questions

  • Count Tiles in 1D OthelloOA · Seen Oct 2021

Similar questions at other companies

  • Sum Dynamic Weighted Tree DistancesJuspay · OA
  • Minimum Fuel Cost Between CitiesMicrosoft · OAMicrosoft interview questions
  • Drone Delivery with Battery Swap StationsCisco · OACisco interview questions
  • Optimal TransferSuperhuman · OASuperhuman interview questions
  • Minimum Travel Time With Periodic Fast RoadsAdobe · OAAdobe interview questions
  • Find the PathLinkedIn · OALinkedIn interview questions
  • Energy CrisisRubrik · OARubrik interview questions
  • Best Telescope SiteAtlassian · OAAtlassian interview questions
  • Cheapest Flight with Its PathAirbnb · OA · ONSITE INTERVIEWAirbnb interview questions
  • Traveling the GraphsOptiver · OAOptiver interview questions
See Money Forward hiring insights
Saved
class Solution {
    public int computeNumberOfLocations(int N, int M, int L, int[] g, int[][] roads) {
      // write your code here
    }

}
Checking account…