From edfb6e5cc93d7449ee0718bd85d1b24a77ee573a Mon Sep 17 00:00:00 2001
From: akmhmgc <akimuhamaguchi@icloud.com>
Date: Fri, 3 Oct 2025 11:11:56 +0900
Subject: [PATCH] 50

---
 50/step1.md | 85 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 50/step2.md | 68 ++++++++++++++++++++++++++++++++++++++++++
 50/step3.md | 17 +++++++++++
 50/step4.md |  1 +
 4 files changed, 171 insertions(+)
 create mode 100644 50/step1.md
 create mode 100644 50/step2.md
 create mode 100644 50/step3.md
 create mode 100644 50/step4.md

diff --git a/50/step1.md b/50/step1.md
new file mode 100644
index 0000000..79f7ccd
--- /dev/null
+++ b/50/step1.md
@@ -0,0 +1,85 @@
+# step1 何も見ずに解く
+
+普通に計算しようと思ったが、n の最大が 2^31 - 1 なので線形時間だと 1 秒以内に間に合わない。
+
+```ruby
+# @param {Float} x
+# @param {Integer} n
+# @return {Float}
+def my_pow(x, n)
+    res = 1
+    n.abs.times do
+        if n < 0
+            res /= x
+        else
+            res *= x
+        end
+    end
+    res
+end
+```
+
+再帰とメモ化で n を半分ずつに分けて計算すれば O(logN)に計算量を落とせるので間に合うのではないかと考えた。
+空間計算量も O(logN)になる
+
+```ruby
+# @param {Float} base
+# @param {Integer} exsp
+# @return {Float}
+def my_pow(base, exsp)
+    exsp_to_pow = {}
+    calculate_my_pow = lambda do |exsp|
+        return 1 if exsp.zero?
+        return base if exsp == 1
+        return exsp_to_pow[exsp] if exsp_to_pow.key?(exsp)
+
+        result = 1.0
+        exsp_abs = exsp.abs
+        if exsp_abs.even?
+            exsp_left = exsp_right = exsp_abs / 2
+        else
+            exsp_left = exsp_abs / 2
+            exsp_right = (exsp_abs + 1) / 2
+        end
+        if exsp >= 0
+            result *= calculate_my_pow.call(exsp_left)
+            result *= calculate_my_pow.call(exsp_right)
+        else
+            result /= calculate_my_pow.call(exsp_left)
+            result /= calculate_my_pow.call(exsp_right)
+        end
+        exsp_to_pow[exsp] = result
+        result
+    end
+    calculate_my_pow.call(exsp)
+end
+```
+
+calculate_my_pow では`exsp`が正の場合だけ計算して、外で exsp が負であれば割るのも良いかも。
+Ruby の冪乗を計算するための`Integer#**`メソッドも時間計算量 O(log)になっているか気になったのでコードを見た。
+バイナリ法という方法で計算することにより、同じ値を計算する必要がないのでメモ化がいらない。
+時間計算量は O(logN)
+参考にすると以下のようになる。
+
+```ruby
+# @param {Float} base
+# @param {Integer} exsp
+# @return {Float}
+def my_pow(base, exsp)
+    return 1 if exsp == 0
+    return base if exsp == 1
+
+    exsp = exsp.abs
+    power = 1
+    current_base = base
+    bit = exsp
+    while bit > 0
+        if (bit & 1) == 1
+          power *= current_base
+        end
+        current_base *= current_base
+        bit = bit >> 1
+    end
+    exsp < 0 ? 1 / power : power
+end
+```
diff --git a/50/step2.md b/50/step2.md
new file mode 100644
index 0000000..66ccdc1
--- /dev/null
+++ b/50/step2.md
@@ -0,0 +1,68 @@
+# step2 他の方の解答を見る
+
+https://github.com/TORUS0818/leetcode/pull/47
+
+step1の再帰の方法であったとしても、子ノードが一つしか生まれないようにすればメモ化が必要なくなるのか。
+exponentが偶数のときは、exponentを半分に減らせて子ノードは1つしかできない。
+奇数のときは次のノードのexponentが偶数になるようにすれば良い。
+
+```ruby
+# @param {Float} base
+# @param {Integer} exponent
+# @return {Float}
+def my_pow(base, exponent)
+  return 1 if exponent.zero?
+  return 1.0 / my_pow(base, - exponent) if exponent < 0
+
+  if exponent.even?
+      return my_pow(base, exponent / 2) ** 2
+  else
+      return base * my_pow(base, exponent - 1)
+  end
+end
+```
+
+こっちはもちろんノードが二つになるので以下だと時間以内に解けない
+
+```ruby
+# @param {Float} base
+# @param {Integer} exponent
+# @return {Float}
+def my_pow(base, exponent)
+  return 1 if exponent.zero?
+  return 1.0 / my_pow(base, - exponent) if exponent < 0
+
+  if exponent.even?
+      # ノードが二つになる
+      return my_pow(base, exponent / 2) * my_pow(base, exponent / 2)
+  else
+      return base * my_pow(base, exponent - 1)
+  end
+end
+```
+
+https://github.com/TORUS0818/leetcode/pull/47#discussion_r2038337006
+確かに bit を 1 にして左にシフトしていくことで捜査する方が自然
+
+```ruby
+# @param {Float} base
+# @param {Integer} exponent
+# @return {Float}
+def my_pow(base, exponent)
+    return 1 if exponent == 0
+
+    if exponent < 0
+        base = 1.0 / base
+        exponent = - exponent
+    end
+    pow = 1
+    current_base = base
+    bit = 1
+    while bit <= exponent
+        pow *= current_base if (exponent & bit) != 0
+        current_base *= current_base
+        bit <<= 1
+    end
+    pow
+end
+```
diff --git a/50/step3.md b/50/step3.md
new file mode 100644
index 0000000..0073fb4
--- /dev/null
+++ b/50/step3.md
@@ -0,0 +1,17 @@
+# step3 3回続けて10分以内に書いてエラーを出さなければOKとする
+
+```ruby
+# @param {Float} base
+# @param {Integer} exponent
+# @return {Float}
+def my_pow(base, exponent)
+    return 1 if exponent.zero?
+    return 1.0 / my_pow(base, -exponent) if exponent < 0
+
+    if exponent.even?
+        return my_pow(base, exponent / 2) ** 2
+    else
+        return base * my_pow(base, exponent - 1)
+    end
+end
+```
diff --git a/50/step4.md b/50/step4.md
new file mode 100644
index 0000000..5941ee1
--- /dev/null
+++ b/50/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正