diff options
author | jack <[email protected]> | 2024-06-17 20:20:39 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-17 20:20:39 -0600 |
commit | ff951b7481190032cb8271a29bd9634c565afb3a (patch) | |
tree | d54135cd2610915ff24195c906078d70e0c9658a | |
parent | 6f7d7ab5663f2880f3b18dc75dfd236f4417f272 (diff) | |
download | leetcode-ff951b7481190032cb8271a29bd9634c565afb3a.tar.gz leetcode-ff951b7481190032cb8271a29bd9634c565afb3a.zip |
754. reach a number
-rw-r--r-- | reach_number.c | 33 | ||||
-rw-r--r-- | reach_number.py | 37 |
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)) |