Question

754. Reach a Number

中文文档

Description

You are standing at position 0 on an infinite number line. There is a destination at position target.

You can make some number of moves numMoves so that:

• On each move, you can either go left or right.
• During the ith move (starting from i == 1 to i == numMoves), you take i steps in the chosen direction.

Given the integer target, return _the minimum number of moves required (i.e., the minimum _numMoves_) to reach the destination_.

 

Example 1:

Input: target = 2
Output: 3
Explanation:
On the 1st move, we step from 0 to 1 (1 step).
On the 2nd move, we step from 1 to -1 (2 steps).
On the 3rd move, we step from -1 to 2 (3 steps).

Example 2:

Input: target = 3
Output: 2
Explanation:
On the 1st move, we step from 0 to 1 (1 step).
On the 2nd move, we step from 1 to 3 (2 steps).

 

Constraints:

• -109 <= target <= 109
• target != 0

Solutions

Solution 1

class Solution:
  def reachNumber(self, target: int) -> int:
    target = abs(target)
    s = k = 0
    while 1:
      if s >= target and (s - target) % 2 == 0:
        return k
      k += 1
      s += k

class Solution {
  public int reachNumber(int target) {
    target = Math.abs(target);
    int s = 0, k = 0;
    while (true) {
      if (s >= target && (s - target) % 2 == 0) {
        return k;
      }
      ++k;
      s += k;
    }
  }
}

class Solution {
public:
  int reachNumber(int target) {
    target = abs(target);
    int s = 0, k = 0;
    while (1) {
      if (s >= target && (s - target) % 2 == 0) return k;
      ++k;
      s += k;
    }
  }
};

func reachNumber(target int) int {
  if target < 0 {
    target = -target
  }
  var s, k int
  for {
    if s >= target && (s-target)%2 == 0 {
      return k
    }
    k++
    s += k
  }
}

/**
 * @param {number} target
 * @return {number}
 */
var reachNumber = function (target) {
  target = Math.abs(target);
  let [s, k] = [0, 0];
  while (1) {
    if (s >= target && (s - target) % 2 == 0) {
      return k;
    }
    ++k;
    s += k;
  }
};