aboutsummaryrefslogtreecommitdiff
path: root/num_ways_remain_place.py
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /num_ways_remain_place.py
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'num_ways_remain_place.py')
-rw-r--r--num_ways_remain_place.py34
1 files changed, 34 insertions, 0 deletions
diff --git a/num_ways_remain_place.py b/num_ways_remain_place.py
new file mode 100644
index 0000000..7204a3f
--- /dev/null
+++ b/num_ways_remain_place.py
@@ -0,0 +1,34 @@
+# 1269. Number of Ways to Stay in the Same Place After Some Steps
+
+"""
+you have a pointer at index 0 in an array of size 'arr_len'. at each step,
+you can move 1 position to the left, 1 position to the right in the array, or
+stay in the same plae. given two integers 'steps' and 'arr_len' return the
+number of ways such that your pointer is still at index 0 after exactly
+'steps' steps. since the answer may be too large, return it modulo 10e9+7
+"""
+
+
+class Solution(object):
+ def dfs(self, steps, arr_len, pos):
+ if pos < 0 or pos >= arr_len:
+ return 0
+ if steps == 0:
+ return 1 if pos == 0 else 0
+ return (
+ self.dfs(steps - 1, arr_len, pos - 1)
+ + self.dfs(steps - 1, arr_len, pos)
+ + self.dfs(steps - 1, arr_len, pos + 1)
+ )
+
+ def numWays(self, steps, arr_len):
+ if steps is None or steps < 0 or not arr_len:
+ return 0
+ return self.dfs(steps, arr_len, 0)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.numWays(3, 2)) # expect: 4
+ print(obj.numWays(2, 4)) # expect: 2
+ print(obj.numWays(4, 2)) # expect: 8