https://leetcode.com/problems/reach-a-number

Let us look at several first steps and understand, which numbers we can reach.

  1. n = 1, numbers we can reach are -1, 1
  2. n = 2, numbers we can reach are -3, -1, 1, 3.
  3. n = 3, numbers we can reach are -6, -4, -2, 0, 2, 4, 6
  4. n = 4, numbers we can reach are -10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10
  5. n = 5, numbers we can reach are -15, -13, ..., 13, 15
  6. n = 6, numbers we can reach are -21, -19, ..., 19, 21

What we can notice looking at these numbers are 2 things:

  1. We always have continious range either in odd or in even numbers.
  2. We have odd -> even -> even -> odd period, depending on n. How we can get it? Sum of numbers from 1 to n is n*(n+1)/2 and parity of number depends only on this number and will not change if we replace some of + to -.

So, we need to find smallest integer. n, such that n*(n+1)/2 >= target, or n^2 + n - 2*target >= 0. This can solved as quadratic equation with solution bound = ceil(sqrt(2*abs(target)+0.25) - 0.5). Also we need to fix odd/even of our number. If we have bound = 10 for example and even target, we need to choose bound = 11: smallest bound more or equal to 10, such that final answer can be even. Similarly we need to check all other cases.

Complexity: if we assume that we can take sqrt in O(1) complexity, then all complexity of algorithm is O(1), both for time and space.

class Solution:
    def reachNumber(self, target):
        bound = ceil(sqrt(2*abs(target)+0.25) - 0.5)
        if target % 2 == 0:
            if bound % 4 == 1: bound += 2
            if bound % 4 == 2: bound += 1
        else:
            if bound % 4 == 3: bound += 2
            if bound % 4 == 0: bound += 1
                
        return bound

If you like the solution, you can upvote it on leetcode discussion section: Problem 0754