aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-17 20:20:39 -0600
committerjack <[email protected]>2024-06-17 20:20:39 -0600
commitff951b7481190032cb8271a29bd9634c565afb3a (patch)
treed54135cd2610915ff24195c906078d70e0c9658a
parent6f7d7ab5663f2880f3b18dc75dfd236f4417f272 (diff)
downloadleetcode-ff951b7481190032cb8271a29bd9634c565afb3a.tar.gz
leetcode-ff951b7481190032cb8271a29bd9634c565afb3a.zip
754. reach a number
-rw-r--r--reach_number.c33
-rw-r--r--reach_number.py37
2 files changed, 70 insertions, 0 deletions
diff --git a/reach_number.c b/reach_number.c
new file mode 100644
index 0000000..90d0ffa
--- /dev/null
+++ b/reach_number.c
@@ -0,0 +1,33 @@
+// 754. Reach a Number
+#include "leetcode.h"
+
+/*
+ * you are standing at position zero 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
+ * i'th 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 to reach the destination
+ */
+
+int reachNumber(int target) {
+ target = abs(target);
+ int step = sqrt(target * 2);
+ int k = (step + 1) * step / 2;
+ if (k == target)
+ return step;
+ if (k < target)
+ step++;
+ while (1) {
+ k = (step + 1) * step / 2;
+ if (!((k - target) % 2))
+ return step;
+ step++;
+ }
+ return -1;
+}
+
+int main() {
+ printf("%d\n", reachNumber(2)); // expect: 3
+ printf("%d\n", reachNumber(3)); // expect: 2
+}
diff --git a/reach_number.py b/reach_number.py
new file mode 100644
index 0000000..de65fcd
--- /dev/null
+++ b/reach_number.py
@@ -0,0 +1,37 @@
+# 754. Reach a Number
+import math
+
+"""
+you are standing at position zero 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
+i'th 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 to reach the destination
+"""
+
+
+class Solution(object):
+ def reachNumber(self, target):
+ """
+ :type target: int
+ :rtype: int
+ """
+ bound = math.ceil(math.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 __name__ == "__main__":
+ obj = Solution()
+ print(obj.reachNumber(2))
+ print(obj.reachNumber(3))