EasyRating 1189

3461. Check If Digits Are Equal in String After Operations I

mathstringsimulationcombinatoricsnumber-theory

解題說明

Check If Digits Are Equal in String After Operations I

題目描述：給定一個由數字組成的字串 s。反覆執行以下操作直到字串長度變為 2：對每對相鄰數字取和再模 10，產生一個新的、長度減 1 的字串。判斷最終剩下的兩個數字是否相等。

解題思路：由於 Easy 版本字串長度較小，可以直接模擬整個過程。每一輪將字串從長度 n 縮減為 n-1，直到長度為 2。每輪中，新字串的第 i 個字元為 (s[i] + s[i+1]) % 10。最終比較兩個剩餘數字是否相等。

C++ 解法

複雜度分析

時間複雜度：O(n²) — 共 n-2 輪，第 i 輪處理長度 n-i 的字串，總計 O(n²)。

空間複雜度：O(n) — 每輪產生的新字串最長為 n。

虛擬碼

1. While s.length > 2:
   a. Create new string: for each i, new[i] = (s[i] + s[i+1]) % 10
   b. Replace s with new string
2. Return s[0] == s[1]

其他解法

組合數學 O(n)：最終的兩個數字是原始數字的加權和（權重為 Pascal 三角形的二項式係數，模 10）。可以直接計算 sum(C(n-2, i) * s[i]) mod 10 和 sum(C(n-2, i) * s[i+1]) mod 10 來判斷，但需要處理模 10 下的二項式係數（使用 Lucas 定理）。

原地模擬 O(n²)：不產生新字串，直接在原始陣列上覆寫。節省空間但邏輯相同。

延伸思考

如果字串長度達到 10⁵，模擬法的 O(n²) 會超時，如何用 Lucas 定理在 O(n) 內求解？
如果取模的數不是 10 而是任意質數 p，問題會更簡單還是更難？
如果要判斷最終所有剩餘數字是否都相等（不限於長度 2），如何推廣？

Check If Digits Are Equal in String After Operations I — CaffeCode