Find a given number is reachable or not

1,317.3K Views

There is number line ranging from -infinity to +infinity. Initially you are number 0. you can move in both directions(Moving left would decrease the number and moving right would increase the number). The condition is that in the ith step you have to iterate i numbers only, you can not stop in the middle. Now you have to tell that, whether a given number is reachable or not.

For example you can reach number 2 in following steps (0,1), (1,-1), (-1,2).

Also you need to provide the optimal solution to reach a given number if its reachable.

Share
Pranav Jain Scholar Asked on 26th April 2016 in Puzzles.
Add Comment

  • 1 Answer(s)

    We can approach this problem by realizing that we can reach any integer n by making repeated jumps of size 1, alternating between moving to the left and moving to the right. Specifically, to reach n, we can make the following jumps:

    1. Move 1 unit to the right
    2. Move 2 units to the left
    3. Move 3 units to the right
    4. Move 4 units to the left
    5. Move 5 units to the right
    6. Move 6 units to the left
    7. and so on, continuing to alternate directions and increasing the size of the jump by 1 each time

    This sequence of jumps will eventually reach n, since the sum of the jump sizes is 1 – 2 + 3 – 4 + 5 – 6 + … = 1 + (3 – 2) + (5 – 4) + (7 – 6) + … is an infinite series that diverges to infinity.

    To find the optimal solution to reach a given number n, we can first check if it is reachable by computing the sum of the first k integers, where k is the smallest positive integer such that n is less than or equal to the sum. If n is not reachable, we can stop and return “not reachable”. Otherwise, we can find the sequence of jumps as follows:

    1. Start at 0
    2. Move 1 unit to the right
    3. Move 2 units to the left, unless we have already reached n
    4. Move 3 units to the right, unless we have already reached n
    5. Move 4 units to the left, unless we have already reached n
    6. Continue alternating between left and right, increasing the jump size by 1 each time, until we reach n.

    This algorithm will terminate after at most 2n steps, since the sum of the jump sizes is at most 1 + 2 + … + n = n(n+1)/2. Therefore, it provides an optimal solution to reach a given number if it is reachable.

    Moshe Expert Answered on 27th March 2023.
    Add Comment
  • Your Answer

    By posting your answer, you agree to the privacy policy and terms of service.
  • More puzzles to try-