content: package question0754;
  
  /**
   * @author qianyihui
   * @date 2019-07-11
   *
   * 虽然LeetCode中标注为简单，但其实是一道困难级别的题。
   *
   * 对于target，如果其值为0，1，3，6，10，15，21……，这很容易算，其结果分别是0，1，2，3，4，5，6……
   *
   * （1）那么如果target不为上述值呢？比如，target为17，怎么办呢？
   *
   * 我们的策略是首先找到比17大的那个数，21，其比17大4，4是偶数，那么我们只需要令其中的第2步往左走即可，步数和走到21相同，6步。
   *
   * （2）如果target为18呢，怎么办呢？其比21小3，是奇数，此时我们要看21的下一个数28，其与18差值为10，因此我们只需令其中的第5步往左走即可，
   * 步数和走到28相同，7步。
   *
   * （3）再举一种情况，如果target值为14呢？其比15小1，是奇数，其比21小7，也为奇数，此时我们继续往下找28，比14大14，是偶数，我们只需令其中
   * 第7步往左走即可，共7步。
   *
   * 为什么上述策略所得到的步数是最小步数呢？
   *
   * 对于（1）和（2）中的情况，可以很好理解，那么对于（3）中的情况呢？
   *
   * 14比15小1，不可能存在将某一步调整为左走就能从15变为14的情况，一旦将某一步调整为左走，其变化量一定是偶数。对于21同理，直到28的情况。
   *
   * 时间复杂度是O(target ^ 0.5)。空间复杂度是O(1)。
   *
   * 执行用时：4ms，击败75.58%。消耗内存：34.1MB，击败56.25%。
   */
  public class Solution {
      public int reachNumber(int target) {
          if (target < 0) {
              target = -target;
          }
          int index = 0, sum = 0;
          while (sum < target || (sum - target) % 2 != 0) {
              ++index;
              sum += index;
          }
          return index;
      }
  }
  