Calculate walking points to reach target

meallhour 0
Viewed 44

  • Given a number (finish end point), then an array of scooters, where scooters represents the position of the ith scooter.

  • Each scooter can travel up to 10 points before the battery is fully discharged, and cannot go further. For example, if the scooter is at point 5, it can travel to points 5, 6, 7, ..., ., up to point 15 (inclusive), but not to point 16 or beyond.

  • Calculate walking steps to reach the target.

Example1:

finish=23, scooters[7, 4, 14] 
output -> solution(finish, scooters) = 4

Explanation1:

  • Starting from 0, the closest scooter is scooters[1] = 4 so it takes 4 points to walk there.
  • Then the scooter can go up to 10 points, 10+4=14.
  • There is a scooter at 14 points (scooters[2] = 14).
  • This way we can go straight to the end to complete 23.
  • So it's a total of 4 points of walking

Example2:

finish=27, scooters[15, 7, 3, 10]
output -> solution(finish, scooters) = 5

My Code:

finish=23
scooters = [7, 4, 14]

def solution(finish, scooters):
    sum = min(scooters)
    step = min(scooters)
    
    while sum < finish:
        step += 10
        sum = sum + step
    
    return step

solution(finish, scooters)

How to include scooters[i] within the while loop to check for the next available scooter?


data-structures python-3.x algorithm python
3 Answers

Simplest way to achieve consistency without too much logic is first sort()ing your list. After that you can calculate any distance between two scooters that has over 10 steps and add it to the sum:

def solution(finish, scooters):
    scooters.append(finish)
    scooters.sort()
    steps = scooters[0]
    for i in range(1, len(scooters)):
        steps += max(0, scooters[i] - scooters[i - 1] - 10)
        if finish in (scooters[i], scooters[i - 1]):
            break

    return steps

print(solution(27, [15, 7, 3, 10]))
# 5
print(solution(23, [7, 4, 14]))
# 4
print(solution(10, [15, 7, 3, 10]))
# 3
print(solution(2, [15, 3]))
# 2
LTJ0

One way to solve this is by counting the number of steps which cannot be taken by scooter. You can do this by creating a list of all the steps that need to be made, populating it with 1s. Then set to 0 any step that can be taken by a scooter. The number of walking steps is then the sum of the list:

def solution(finish, scooters):
    steps = [1 for _ in range(finish+1)]
    zeros = [0 for _ in range(11)]
    for s in scooters:
        steps[s:s+11] = zeros
    return sum(steps)

solution(27, [15, 7, 3, 10])
# 5
solution(23, [7,4,14])
# 4
usergAKD0

As a simple approach, you can just iterate over the scooters array, and increment steps based on the distance between the i-th scooter and the i+1-th scooter.

def solution(finish, scooters):
    i = 0
    n = len(scooters)
    scooters.sort()
    steps = min(scooters[0], finish)
    for i in range(0, n-1):
        if scooters[i] + 10 >= finish:
            break
        elif scooters[i+1] > finish:
            steps += max(0, finish-scooters[i]-10)
        else:
            steps += max(0, scooters[i+1]-scooters[i]-10)
    if scooters[-1] < finish:
        steps += max(0, finish - scooters[-1] - 10)
    return steps

print(solution(27, [15, 7, 3, 10]))
print(solution(23, [7,4,14]))

Time complexity: O(nlogn) where n is the length of scooters array.

Abhinav Mathur0
Related