Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/754.html

754. Reach a Number (Easy)

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

On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps.

Return the minimum number of steps required to reach the destination.

Example 1:

Input: target = 3
Output: 2
Explanation:
On the first move we step from 0 to 1.
On the second step we step from 1 to 3.

Example 2:

Input: target = 2
Output: 3
Explanation:
On the first move we step from 0 to 1.
On the second move we step  from 1 to -1.
On the third move we step from -1 to 2.

Note:

  • target will be a non-zero integer in the range [-10^9, 10^9].
  • Companies:
    InMobi

    Related Topics:
    Math

    Solution 1.

    Try to find pattern:

    Firstly, for numbers n(n+1)/2, they require n steps, where n >= 1. For example, 1 = 1, 3 = 1 + 2, 6 = 1 + 2 + 3

    How to get the numbers inbetween?

    Think of 2: the smallest n(n+1)/2 greater than 2 is 3. If we invert 3’s component 1 or 2, we actually subtract 1*2 or 2*2 from 3. Notice the subtraction is using even number. But 3 - 2 = 1 is an odd number. So we can’t get 2 from 3.

    Consider the next n(n+1)/2, which is 6. 6 - 2 = 4. So we can invert 4 / 2 = 2 in equation 6 = 1 + 2 + 3 to get 2 = 1 - 2 + 3.

    Let’s examine our algorithm with two more test cases.

    For 4, the next n(n+1)/2 is 6. Since 6 - 4 = 2, so we can invert 1 in 6 = 1 + 2 + 3 to get 4 = -1 + 2 + 3.

    For 5:

    • check 6, 6 - 5 = 1, doesn’t work.
    • check 10 = 1+..+4, 10 - 5 = 5, doesn’t work.
    • check 15 = 1+..+5, 15 - 5 = 10. Works! 5 = 1 + 2 + 3 + 4 - 5.

    In sum, keep computing sum = n(n+1)/2. If sum is greater than or equal to target and (sum - target) % 2 == 0, the corresponding n is the answer.

    // OJ: https://leetcode.com/problems/reach-a-number/
    // Time: O(sqrt(T))
    // Space: O(1)
    class Solution {
    public:
        int reachNumber(int target) {
            int i = 0, sum = 0;
            target = abs(target);
            while (sum < target || (sum - target) % 2 != 0) {
                sum += ++i;
            }
            return i;
        }
    };
    
    • class Solution {
          public int reachNumber(int target) {
              target = Math.abs(target);
              if (target == 0)
                  return 0;
              int position = 0;
              int step = 0;
              while (position < target || position % 2 != target % 2) {
                  step++;
                  position += step;
              }
              return step;
          }
      }
      
      ############
      
      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;
              }
          }
      }
      
    • // OJ: https://leetcode.com/problems/reach-a-number/
      // Time: O(sqrt(T))
      // Space: O(1)
      class Solution {
      public:
          int reachNumber(int target) {
              int i = 0, sum = 0;
              target = abs(target);
              while (sum < target || (sum - target) % 2 != 0) {
                  sum += ++i;
              }
              return i;
          }
      };
      
    • 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(object):
          def reachNumber(self, target):
              """
              :type target: int
              :rtype: int
              """
              target = abs(target)
              k = 0
              sum = 0
              while sum < target:
                  k += 1
                  sum += k
              d = sum - target
              if d % 2 == 0:
                  return k
              return k + 1 + (k % 2)
      
    • 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;
          }
      };
      
      

    All Problems

    All Solutions