Minimum distance of a number from origin.


  • 0
    N

    Given a number line from -infinity to +infinity. You start at 0 and can go either to the left or to the right. The condition is that in i’th move, you take i steps.

    1. Find if you can reach a given number x
    2. Find the most optimal way to reach a given number x, if we can indeed reach it. For example, 3 can be reached in 2 steps, (0, 1) (1, 3) and 4 can be reached in 3 steps (0, -1), (-1, 1) (1, 4)

  • 0
    S

    One can always reach any of the numbers...
    Right,left,right,left
    Or left, right, left, right...
    Every left and right, you move right one step...


  • -1

    The condition is that in i’th move, you take i steps.

    [...]

    4 can be reached in 3 steps (0, -1), (-1, 1) (1, 4)

    In three moves, not in three steps.

    Find the most optimal way to reach a given number x

    Just always walk towards it. Or one step away if you have to complete moves (it's not clear, but I guess you have to because otherwise it makes no sense to talk about moves at all) and are in the middle of a move and already on the goal. For example, to reach 11:

    First move: 0 -> 1
    Second move: 1 -> 2 -> 3
    Third move: 3 -> 4 -> 5 -> 6
    Fourth move: 6 -> 7 -> 8 -> 9 -> 10
    Fifth move: 10 -> 11 -> 10 -> 11 -> 10 -> 11

    So that took eleven steps and five moves (not clear what you're counting, what "optimal" means).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.