主題

LeetCode - 2117. Abbreviating the Product of a Range 解題心得

Not In My Back Yard | 2022-06-18 12:00:11 | 巴幣 0 | 人氣 54

題目連結:


題目意譯:
你被給定兩個正整數 left 和 right,其中 left ≦ right。請計算出 [left, right] 這個範圍(含左右端點)中所有數字的乘積。

由於此乘積值可能會很大,你必須按照以下步驟將其簡寫化:
1. 數這個乘積有多少個末尾零並將它們移除掉。令其數量為 C 個。
例如,1000 之中有 3 個末尾零,而 546 中有 0 個末尾零。

2. 乘積值剩餘的位數長稱為 d。如果 d > 10,則將其值表示為 <pre>...<suf>,其中 <pre> 代表乘積值的開頭 5 位數而 <suf> 為乘積值的移除所有末尾零後的結尾 5 位數;如果 d ≦ 10,則保持不變。
例如,我們將 1234567654321 表示為 12345...54321,但是 1234567 將表示為 1234567。

3. 最後,將乘積值表為字串 "<pre>...<suf>eC"。
例如,12345678987600000 將表為 "12345...87876e5"。

回傳一字串其代表著 [left, right] 這個範圍(含左右端點)中所有數字的乘積之簡寫。

限制:
1 ≦ left ≦ right ≦ 10 ^ 4



範例測資:
範例 1:
輸入: left = 1, right = 4
輸出: "24e0"
解釋: 乘積值為 1 × 2 × 3 × 4 = 24。
該值沒有末尾零,所以 24 保持不變。簡寫將以 "e0" 作結。
由於位數長為 2,其值小於 10,因此我們不需要進一步將 24 簡化。
因此,最終的簡寫為 "24e0"。

範例 2:
輸入: left = 2, right = 11
輸出: "399168e2"
解釋: 乘積值為 39916800。
該值有 2 個末尾零,將其移除後得 "399168"。簡寫將以 "e2" 作結。
移除末尾零後的位數長為 6,所以我們不需要進一步簡化。
因此,簡化後的乘積值為 "399168e2"。

範例 3:
輸入: left = 371, right = 375
輸出: "7219856259e3"
解釋: 乘積值為 7219856259000。


解題思維:
------------------前言開始--------------------
Python 、 Java 表示:EZ
C++ 表示:好啊,都這樣啊
------------------前言結束--------------------
是的,本題對於 C++ 極度地不友善。因為 C++ 沒有大數運算,不能偷懶(雖然可以自己寫,如這題)。因此,我們需要一些數學:
首先由於題目的簡化之規則,我們需要把 [left, right] 中的所有 2 、 5 之質因數全部挑出來(因為 1 個 2 配上 1 個 5 就會形成一個末尾零),之後再處理。

這邊假設 [left, right] 中有 a 個 2 、 b 個 5 之因數(也就是 left × (left + 1) × …… × right 質因數分解後將包含 2 ^ a 和 5 ^ b)。

因此,可以看到末尾零的數量將是 Z = max(a, b)。令 R = (2 ^ a) × (5 ^ b) ÷ Z,也就是湊完 10 之後剩下的 2(或 5)之質因數。

然後,我們可以先試乘看看剩下的數字(包含 2 、 5 以外的質因數以及 R 之值)之乘積值會不會超過 10 ^ 10(也就是看乘積值有沒有超過 10 位數,long long 型態最大可以到 18 位數左右)。

如果沒有則簡化過程就到此為止,此時乘積值與 "e" 以及 Z 值串接在一起即為簡寫後的乘積值;反之,則會比較麻煩:
首先末五位數字比較好處理,只要利用餘數的特性即可——「先取餘數再運算再取一次餘數」與「運算後取餘數」的結果是相同的。因此,我們把剩下的質因數(記得包含 R)乘在一起的時候一直取除以 100000 的餘數,最後即可獲得乘積值的末五位數。

接著,高中的時候應該會上過以 10 為底的對數函數 log10 有一特性——即 log10(N) = x + y (其中 0 ≦ y < 1)中的指數部分 x 加 1 即為 N 的位數長,而對於本題來說更重要的是尾數 y 的部分,即 log10(k) ≦ 10 ^ y < log10(k + 1),其中 k 為 N 的開頭數字。

但是實際上這個尾數的性質可以再推廣,也就是 k 可以不僅限於一位數(假設其為 L 位數長),即 log10(k) ≦ 10 ^ (y + L - 1) < log10(k + 1)。因此我們可以藉由在計算乘積值末五位的時候順便把剩下的質因數(包含 R)之各自對數值加總,求出其對於的尾數 y。此時便可以從 10 ^ (y + 4) 取整數部分推得乘積值的開頭五位數。

最後把開頭、結尾各自五位數以「...」相接再串接上 'e' 和 Z 之值即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作