FastPrepRunning Through Walls with Limited Energy

Running Through Walls with Limited Energy

Scale AI logoScale AI● HardNEW GRADOA
Learn

Problem statement

You start at integer coordinate 0 on a number line with energy energy. A unit move crosses the gap between two adjacent integers.

A wall position x represents a wall at x+0.5. Crossing that gap in either direction costs its positive thickness; every gap without a wall costs 1. Every crossing costs energy, including repeated crossings of the same wall.

Return the maximum number of distinct walls that can be crossed while spending at most energy.

Function

maximumDistinctWalls(energy: long, wallPositions: int[], thicknesses: int[]) → int

Examples

Example 1

energy = 4wallPositions = [-1,0]thicknesses = [2,2]return = 1

Either adjacent wall costs 2. Crossing both requires visiting both sides and costs 6.

Example 2

energy = 6wallPositions = [-1,0]thicknesses = [2,2]return = 2

Cross one wall, return through it, then cross the other: 2+2+2.

Example 3

energy = 5wallPositions = [0,2]thicknesses = [3,1]return = 2

Moving right crosses the first wall for 3, one ordinary gap for 1, and the second wall for 1.

Constraints

  • 0 <= wallPositions.length == thicknesses.length <= 200000.
  • Wall positions are unique integers in [-1000000000,1000000000].
  • 1 <= thicknesses[i] <= 1000000000.
  • 0 <= energy <= 10^18.

More Scale AI problems

See Scale AI hiring insights
public int maximumDistinctWalls(long energy, int[] wallPositions, int[] thicknesses) {
    // write your code here
}
energy4
wallPositions[-1,0]
thicknesses[2,2]
expected1
Checking account…