aboutsummaryrefslogtreecommitdiff
path: root/other/num_ways_remain_place.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/num_ways_remain_place.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/num_ways_remain_place.cpp')
-rw-r--r--other/num_ways_remain_place.cpp32
1 files changed, 32 insertions, 0 deletions
diff --git a/other/num_ways_remain_place.cpp b/other/num_ways_remain_place.cpp
new file mode 100644
index 0000000..eee14e5
--- /dev/null
+++ b/other/num_ways_remain_place.cpp
@@ -0,0 +1,32 @@
+// 1269. Number of Ways to Stay in the Same Place After Some Steps
+#include "leetcode.h"
+
+/*
+ * 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 {
+public:
+ int numWays(int steps, int arr_len) {
+ int n = min(steps / 2 + 1, arr_len);
+ vector<int> v1(n + 2), v2(n + 2);
+ v1[1] = 1;
+ while (steps--) {
+ for (auto i = 1; i <= n; ++i)
+ v2[i] = ((long)v1[i] + v1[i - 1] + v1[i + 1]) % 1000000007;
+ swap(v1, v2);
+ }
+ return v1[1];
+ }
+};
+
+int main() {
+ Solution obj;
+ printf("%d\n", obj.numWays(3, 2)); // expect: 4
+ printf("%d\n", obj.numWays(2, 4)); // expect: 2
+ printf("%d\n", obj.numWays(4, 2)); // expect: 8
+}